acwing 202题解

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll ksc(ll x,ll y,ll p)
{
    ll res=0;while(y){if(y&1)res=(res+x)%p;x=(x<<1)%p; y>>=1;}return res;
}

ll qp(ll a,ll b,ll c)
{
    ll res=1;
    while(b)
    {
        if(b&1) { res=ksc(res,a,c); b--; }
        a=ksc(a,a,c);
        b>>=1;
    }
    return res%c;
}

ll ol(ll x)
{
    ll res=x;
    for(ll i=2;i*i<=x;i++)
    {
        if(x%i==0)
        {
            res=res/i*(i-1);
            while(x%i==0) x/=i;
        }
    }
    if(x!=1) res=res/x*(x-1);
    return res;
}

int main()
{
    ll t,l;
    for(t=1;;t++)
    {
        ll ans;
        scanf("%lld",&l);
        if(!l) break;
        ll c=9*l/(__gcd(8ll,l));
        if(__gcd(10ll,c)!=1)
        {
            printf("Case %lld: 0\n",t);
        }
        else
        {
            ll cnt=ol(c);
            ans=cnt;
            for(ll i=1;i*i<=cnt;i++)
            {
                if(cnt%i==0)
                {
                    if(qp(10ll,i,c)==1) ans=min(ans,i);
                    if(qp(10ll,cnt/i,c)==1) ans=min(ans,cnt/i);
                }
            }
            printf("Case %lld: %lld\n",t,ans);
        }
    }
    return 0;
}