POJ1426 Find The Multiple 题解

原题

啊，不小心拖黑了
https://vjudge.net/contest/347799#problem/F

题目大意

求n(n <= 200)的一个倍数，其只由0和1组成

题目分析

第一眼:100位啊，写个高精度
第二眼:这也叫搜索？
听完题解:这 * * 还不用写高精度？
没错，我的程序跑n=6的时候输出1110，跑n=9的时候输出9条1，就算n=198也只是19位
而$log_{10}2^{64}=19.26591972249477$log10​264=19.26591972249477
好吧，也并不能说只是，反正unsigned long long就可以了
下面是不会数学的人写的程序

代码

#include<cstdio>
#include<cstring>

int m[110];
int mod(int* a,int size,int b)
{
    int p = a[0];
    int t = 1;
    while (t < size)
    {
        while (p < b && t < size) 
        {
            p *= 10;
            p += a[t++];
        }
        p %= b;
    }
    return p;
}
void inc(int* a,int& size)//不是真正意义上的加1
{
    int* p = a + size - 1;
    while (*p != 0 && p != a)*p = 0,p--;
    if (p == a) size++;
    *p = 1;
}
int main()
{
while (true)
{
    int n,sm;
    memset(m,0,sizeof(m));
    m[0] = 1;sm = 1;
    scanf("%d",&n);
    if(n == 0) break;
    while (true)
    {
        inc(m,sm);
        if (mod(m,sm,n) == 0) 
        {
            for (int i = 0;i < sm;i++) printf("%d",m[i]);
            putchar(10);
            break;
        }
    }
}
return 0;
}