ai = x ai-1 + y 递推容易得到 x^n -1 = m a0/t a0' = a0 / gcd(a0,t) 即 ： x^n = 1 mod (a0') 在gcd (x,a0') != 1 时候无解 化简下来就是一个A^B = C mod D的形式，已知A，C，D，求解B。 其实很显然这是一个离散对数问题，这题比较特殊的是化简之后C = 1，也很容易的想到欧拉定理a ^ f(n) = 1 mod n， 题解就是枚举f(n)的各个因子，求出最小的 证明： x = g x' a0' = g a0'' g^n x^n = a0''gm + 1 g ( g^(n-1) x^n -m*a0'' ) = 1 在g > 1 时候 无解。 然后就容易了。求一下欧拉函数，枚举约数即可。

#include <iostream>
#include <cmath>
#include <string>
using namespace std;
#define FOR(i,s,e) for (int (i)=(s); (i)<(e); i++)
/*求素数[1,MAXPRI]*/
const int MAXPRI=50000+10;
bool NotPrime[MAXPRI];
int  PrimeList[MAXPRI];
void Prime()
{
    int i,j,up = sqrt(MAXPRI*1.0);
    memset(NotPrime,0,sizeof(NotPrime));
    memset(PrimeList,0,sizeof(PrimeList));
    for(i = 2; i <= up; i++) 
    {
        if(NotPrime[i] == 0)
        {
            PrimeList[++PrimeList[0]] = i;
            for(j = i + i; j < MAXPRI*1.0; j = j + i)
                NotPrime[j] = 1;
        }
    }
    for(i = up + 1; i < MAXPRI; i++)
        if(NotPrime[i] == 0)
            PrimeList[++PrimeList[0]] = i;
}
__int64  euler(__int64  x)
{
    int i ;
    __int64  res = x,up = (__int64 )sqrt(x * 1.0) + 1;
    for (i = 1; PrimeList[i] < up && i < PrimeList[0]; i++)
    if (x % PrimeList[i] == 0)
    {
        res = res / PrimeList[i] *( PrimeList[i] - 1);
        while (x % PrimeList[i] == 0 )
            x/=PrimeList[i];
     }
    if (x > 1)
        res = res / x * (x-1);
    return res;
}

__int64 gcd(__int64 a, __int64 b)
{
    if (a < b)
        return gcd(b,a);
    __int64 c ;
    while (b) 
    {
        c=a%b;
        a=b;
        b=c;
    }
    return a;
}
__int64  power_mod(__int64 A, __int64  B, __int64 C)
{
    __int64  R = 1, D = A;
    while (B )
    {
        if (B&1) R = (R*D)%C;
        D = (D*D)%C;
        B >>=1;
    }
    return R;
}

int main()
{
    __int64 x,y,a0,t;
    __int64 min,ph;
    Prime();
    while (scanf("%I64d%I64d%I64d",&x,&y,&a0)!=EOF)
    {
        t = y / (x-1);
        if (t % a0 == 0)  
        {
            printf("1\n");
            continue;
        }
        __int64 temp = gcd(a0,t);
        a0 = a0 / temp;
        if  (gcd(x,a0) != 1)
        {
            printf("Impossible!\n");
            continue;
        }
        /*A^B = C MOD D,其中A=X，C=1，D=a0， 求B*/
        ph = euler(a0);
        min = ph;
        for (int i=1; i*i<=ph; i++)
        if (ph % i == 0)
        {
            if (i<min && power_mod(x,i,a0) == 1)
                min = i;
            if (ph/i < min && power_mod(x,ph/i,a0) == 1)
                min = ph/i;
        }
        printf("%I64d\n",min);

    }
    return 0;
}