Project Euler 303 Multiples with small digits

Posted on | | 阅读数 次
Words count in article: 606 | Reading time ≈ 2

开启传送门

题目描述

For a positive integer $n$, define $f(n)$ as the least positive multiple of $n$ that, written in base $10$, uses only digits $≤ 2$.

Thus $f(2)=2, f(3)=12, f(7)=21, f(42)=210, f(89)=1121222$.

Also,$ \sum_{n=1}^{100} \frac{f(n)}{n} = 11363107 $

Find $ \sum_{n=1}^{10000} \frac{f(n)}{n}. $

题意

问你对于每个数字来说，找到他的一个最小整数倍，使得最小整数倍在十进制下每位都小于3

分析

很显然，考的是搜索，如何高效搜索．

最简单的想法就是枚举倍数，然后逐个判断是否合法，然后你会发现所有$999$的倍数都Ｔ飞了

然后考虑剪枝，因为可以显然得到，有些倍数一定无效，比如：

$5来说，5\ast 1 = 5,5\ast 11 = 55,5\ast 21 = 105 \dots$

可以显然发现，对于$5$来说，以$1$结尾的倍数显然都不合理，因为他们的最后一位一定是$5$，可以直接判断掉．

然后你就就基本可以过掉大部分数据，但是还是有一个比较头疼，那就是$9999$.

因为他对应的答案贼大，暴力搜索基本都GG．然后我们换一个思路．

那就是我们直接暴力枚举所有的那些看起来长的像$3$进制的十进制数．

然后我们就直接存储所有的这样的数字，然后枚举？

那么显然内存不够，那怎么办呢？

dfs?

还是Ｔ飞，所以我们还要在此基础上剪枝．

首先我们可以构造出一种做法就是，每次搜索的时候得到的都是之前没出现过的最小的这类数字．

然后我们维护一个mod数组，表示当前这个mod正确的情况下，最小的这类数字是多少

然后答案显然就是mod[0]啦…….

代码

给大佬递上我奇丑无比的代码　(/ω＼)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<bits/stdc++.h>
#define ll unsigned long long
using namespace std;
ll vis[10000+100];
ll cal(int a){
	queue<ll> que;
	que.push(1),que.push(2);
	memset(vis,0,sizeof vis);
	vis[1] = 1; vis[2] = 2;
	while(true){
		ll now = que.front(); que.pop();
		if(now%a==0) return now/a;
		for(int i = 0;i<3;i++){
			ll buf = now*10+i;
			ll buff = buf%a;
			if(vis[buff]) continue;
			vis[buff] = buf;
			que.push(buf);
		}
	}
}
int main(){
	ll ans = 0;
	for(int i = 1;i<=10000;i++) ans+=cal(i);
	cout<<ans<<endl;
	return 0;
}