学步园

刚开始花了很长时间化简，求出x^k mod a0=1来却不知道怎么去求解。。。。

看了解题报告，套用欧拉函数，因为 x^φ(a0) mod a0 =1，所以除了无解的情况，最大的解也不会超过φ(a0)，然后比较φ(a0)的因子里，找一个最小的即可。

对于无解的情况，即 Gcd(x,a0)!=1 ，假设存在共同因子m，那么x=x' * m，a0=a0' * m；则 (x' * m)^k - t* (a0' * m) =1 ，化简 m*( x'^k * m^(k-1) - t*a0' )=1，显然，对于m大于1是无解的

code：

#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL __int64
using namespace std;
const int MAXN = 11;
int n;
LL Gcd(LL a, LL b)
{
    return b==0?a:Gcd(b,a%b);
}

LL PowMod(LL n,LL exp,LL mod)
{
    LL ret=1,tmp=n%mod;
    while(exp)
    {
        if(exp&1)
            ret=ret*tmp%mod;
        exp>>=1;
        tmp=tmp*tmp%mod;
    }
    return ret;
}

LL Eular(LL n)
{
    LL fac,ans=1;
    for(fac=2;fac*fac<=n;fac++)
    {
        if(n%fac==0)
        {
            n/=fac;
            ans*=fac-1;
            while(n%fac==0)
            {
                n/=fac;
                ans*=fac;
            }
        }
    }
    if(n>1) ans*=n-1;
    return ans;
}

LL solve(LL x,LL y,LL a0)
{
    if(y==0) return 1;
    LL gcd=Gcd(y/(x-1),a0);
    a0/=gcd;
    if(Gcd(a0,x)!=1) return -1;
    LL lim=Eular(a0);
    LL minn=lim;
    for(LL fac=2;fac*fac<=lim;fac++)
    {
        if(lim%fac==0)
        {
            if(PowMod(x,fac,a0)==1&&fac<minn)
                minn=fac;
            if(PowMod(x,lim/fac,a0)==1&&fac<minn)
                minn=lim/fac;
        }
    }
    return minn;
}

int main()
{
    LL x,y,a0,ans;
    while(~scanf("%I64d%I64d%I64d",&x,&y,&a0))
    {
        ans=solve(x,y,a0);
        if(ans==-1) puts("Impossible!");
        else printf("%I64d\n",ans);
    }
    return 0;
}