POJ1426 Find The Multiple

Poj：1426

http://poj.org/problem?id=1426

方法：枚举+同余模定理

题意：给出一个整数n，(1 <= n <= 200)。求出任意一个它的倍数m，要求m必须只由十进制的'0'或'1'组成。可以保证m的大小低于100位。

思路：参考网上的思路。

假如已知k 现在去判断k*10+1,k*10,是否能整除n

有式子： (k*10+a)%n

=（k%n*10%n+a%n)%n

假如k%n的值已经保存，那么可简化为

= (mod[i-1]*10+a)%

 1 #include<iostream>
 2 #include<stdio.h>
 3 #define ll long long
 4 using namespace std;
 5 const int maxn=1e6;
 6 int n;
 7 int MOD[maxn];
 8 void print(int i){
 9     if (!i) {
10         return;
11     }
12     else{
13         print(i/2);
14         printf("%d",i%2);
15     }
16 }
17 int main()
18 {
19     while(scanf("%d",&n)&&n){
20         MOD[1]=1;
21         int i;
22         for (i=2; MOD[i-1]!=0; ++i) {
23             MOD[i]=(MOD[i/2]*10+i%2)%n;
24         }
25         print(i-1);
26         printf("
");
27     }
28     return 0;
29 }

View Code

走一遍代码就好理解了。假如说我们现在要找7的如题所述的倍数:

MOD(1) = 1

MOD(2) = (MOD(1)*10+0) % 7 = 3 ；MOD(3) = (MOD(1)*10+1) % 7 = 4

MOD(4) = (MOD(2)*10+0) % 7 = 2 ；MOD(5) = (MOD(2)*10+1) % 7 = 3 ；MOD(6) = 5 ；MOD(7) = 6

MOD(8) = 6 ；MOD(9) = 0 ；MOD(10) 结束。

什么意思呢？

因为答案的首位肯定是1

所以我们枚举来看看：

1 % 7 = 1 (mod(1))

10 % 7 = 3(mod(2))

11 % 7 = 4(mod(3))

100 % 7 = 30 % 7 = 2 (mod(4))

101 % 7 = 31 % 7 = 3 (mod(5))

110 % 7 = 40 % 7 = 5 (mod(6))

111 % 7 = 41 % 7 = 6 (mod(7))

实际上思路就是从1开始枚举可能的值，然后存余数对除法进行优化。

那么从另一个方面想：如果m真的有100位，存的下所有可能的余数吗？（MOD数组）

当MOD数组大小开位1e6的时候，AC，说明其实远远找不了那么多。用dfs（限定搜索上限，比如找到第19层就不再向更深处搜索），bfs也可以做。