数学题candy解题反思

唉，考场上只想出了的处理各个位上的数字相加的方法，至于那个11111...111就只有打表得到了一个小数据范围的，但貌似没什么用。所以，在此就只讲正解了。

由题意得，我们需要先把各个位上的数字加起来，求出这个sum的最小质因数，然后对于可看作,即.这个用快速幂解决，快速幂时带个取余操作。完了。

#include<bits/stdc++.h>
using namespace std;

const int maxn = 5e6;

string s;
int prime[maxn+5];
int tot,n,sum,ans;
int mark[maxn+5];

void init()
{
    freopen("candy.in","r",stdin);
    freopen("candy.out","w",stdout);
}

void get()
{
    /*for(int i=2;i<=maxn;i++)
    {
        if(!mark[i])
        {
            prime[++tot]=i;
        }
        for(int j=1;j<=tot;j++)
        {
            if(i*prime[j]>n) break;
            mark[i*prime[j]]=1;
            if(i%prime[j]==0)
            {
                break;
            }
        }
    }*/
    for(int i=2;i<=maxn;i++){
        if(!mark[i])
            mark[i] = i, prime[++tot] = i;
        for(int j=1;j<=tot;j++)
        {
            if(prime[j] > mark[i] || prime[j] > maxn / i) break;
            mark[i * prime[j]] = prime[j];
        }
    }
}

int qpow(int a,int k,int P)
{
    a %= P; int ret = 1;
    while(k){
        if(k & 1) ret = 1LL * ret * a % P;
        a = 1LL * a * a % P;
        k >>= 1;
    }
    return ret;
}

int main()
{
    //init();
    cin>>s;
    n=s.size();
    for(int i=0;i<n;i++)
    {
        sum+=s[i]-'0';
    }
    get();
    for(int i=1;i<=tot;i++)
    {
        if(sum%prime[i]==0||qpow(10,n,9*prime[i])==1)
        {
            printf("%d",prime[i]);
            break;
        }
    }
    return 0;
}