完全想不到啊，同余模定理没学过啊，想起上学期期末考试我问好多同学‘≡’这个符号什么意思，都说不知道，你们不是上了离散可的吗？不过看了别人的解法我现在会了，同余模定理介绍及运用点这里点击打开链接
简单说一下同余模定理：如果(a - b) / m = 0，说明a%m等于b%m，那么对于本题应该如何运用呢? 已知a % n = m，那么(a * 10 + x) % n = a * 10 % n + x % n = (a % n * 10 + x ) % n = (m *10 + x ) % n，有了这个结论，我们在已知111 % m的情况下，一步就能知道1111 % m的值，通过判断余数是否为0来判断是否可以整除m。
举个例子：
如果n = 6
1 % 6 = 1
10 % 6 = 1 * 10 % 6 = 4
11 % 6 = (1 * 10 + 1) % 6 = 5
100 % 6 = (4 * 10) % 6 = 4
101 % 6 = (4 * 10 + 1) % 6 = 5
110 % 6 = (5 * 10) % 6 = 2
111 % 6 = ( 5 * 10 + 1 ) % 6 = 3
....
....
已知递推直到余数为0，利用这种方法就解决了大数问题。
通过这题又学到了新的知识，很有收获。
AC代码
#include<cstdio>
typedef long long LL;
const int maxn = 1e6 + 5;
int mod[maxn], ans[150];
int main(){
int n;
while(scanf("%d", &n) == 1 && n){
mod[1] = 1 % n;
int i;
for(i = 2; mod[i - 1] != 0; ++i) {
mod[i] = (mod[i >> 1] * 10 + i % 2) % n; //暴力枚举当前位(0 or 1)
}
--i;
int c = 0;
while(i) {
ans[c++] = i & 1;
i >>= 1;
}
for(i = c - 1; i >= 0; --i) printf("%d", ans[i]);
printf("\n");
}
return 0;
}
如有不当之处欢迎指出！