51nod1035 最长的循环节

这里写图片描述
题目的实际意义是求 10^x $\equiv$ 1(mod n)
#include <bits/stdc++.h>

using namespace std;

#define LL long long

LL euler_phi(int n)
{
    LL res=n;
    for(int i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            res=res/i*(i-1);
            while(n%i==0)n/=i;
        }
    }
    if(n!=1)res=res/n*(n-1);
    return res;
}


LL mod_pow(LL x,LL n,LL p)
{
    LL res=1;
    while(n)
    {
        if(n&1)res=res*x%p;
        x=x*x%p;
        n>>=1;
    }
    return res;
}





int main()
{
    int n;
    cin>>n;
    LL ans=0,tmp=0,res=0;
    for(LL i=1;i<=n;i++)
    {
        LL t=euler_phi((int)i);
        tmp=0;
        for(int j=1;j<=t;j++)
        {
            if(t%j==0)
            {
                if(mod_pow(10,j,i)==1)
                {
                    tmp=j;
                    break;
                }
            }
        }
        if(tmp>ans)
        {
            ans=tmp;
            res=i;
        }
    }
    cout<<res<<endl;
    return 0;
}