hdu 3307(欧拉函数+好题)

Description has only two Sentences

Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1071 Accepted Submission(s): 323

Problem Description

a_n = X*a_n-1 + Y and Y mod (X-1) = 0.
Your task is to calculate the smallest positive integer k that a_k mod a₀ = 0.

Input

Each line will contain only three integers X, Y, a₀ ( 1 < X < 2³¹, 0 <= Y < 2⁶³, 0 < a₀ < 2³¹).

Output

For each case, output the answer in one line, if there is no such k, output "Impossible!".

Sample Input

2 0 9

Sample Output

1

很好的一个题目。

思路：对于此数列我们可以得到其通项为:

an = a0*xⁿ+ (1+x+x²+..x^n-1)Y = (xⁿ-1)/(x-1)*Y+a0xⁿ

假设ak%a0 = 0,那么我们代入得 ((x^k-1)/(x-1)*Y+a0x^k)%a0 =0 又因为题目中说过Y%（x-1）=0 所以设 Y=Y/（x-1）。

最终我们得到 ak%a0 = (xⁿ-1)*Y%a0 = 0 接下来就是这个题目的难点了，这个地方我至今无法想通，如果有大牛的话请指教一二。

我们得到 d = gcd(Y,a0),那么这个式子就变成了 (xⁿ-1)*(Y/d)%(a0/d) = 0 ,又因为 Y/d 与 a0/d 互质，取模不可能为0，设 a = a0/d 所以最终我们得到:

(xⁿ-1)%a = 0 ----------> xⁿ%a=1 这里就可以根据欧拉定理求解了。

欧拉定理：若n,a为正整数，且n,a互素，则:

这里求出的欧拉函数不一定是最小的解，所以要到它的因子里面去找。

但是我还是想不通为什么要求出最大公约数之后再进行求解？

我在想是不是形如(xⁿ-1)*y%a=0的式子可以都可以变成 (xⁿ-1)%(a/gcd(y,a))=0进行求解???BUT,WHY??

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <stdlib.h>
#include <math.h>
using namespace std;
typedef long long LL;
LL e[100][2];
LL phi(LL x)
{
    LL ans=x;
    for(LL i=2; i*i<=x; i++)
        if(x%i==0)
        {
            ans=ans/i*(i-1);
            while(x%i==0) x/=i;
        }
    if(x>1)
        ans=ans/x*(x-1);
    return ans;
}
LL gcd(LL a,LL b)
{
    return b==0?a:gcd(b,a%b);
}
LL pow_mod(LL a,LL n,LL mod)
{
    LL ans = 1;
    while(n)
    {
        if(n&1) ans=ans*a%mod;
        a=a*a%mod;
        n>>=1;
    }
    return ans;
}
void devide(LL ans,int &id)
{
    for(LL i=2; i*i<=ans; i++) ///分解质因数
    {
        if(ans%i==0)
        {
            e[id][0]=i;
            e[id][1]=0;
            while(ans%i==0) ans/=i,e[id][1]++;
            id++;
        }
    }
    if(ans>1)
    {
        e[id][0]=ans;
        e[id++][1]=1;
    }
}

int main()
{
    LL X,Y,a0;
    while(~scanf("%lld%lld%lld",&X,&Y,&a0))
    {
        Y = Y/(X-1);
        LL d = gcd(Y,a0);
        a0 = a0/d;
        if(gcd(X,a0)!=1)
        {
            printf("Impossible!
");
        }
        else
        {
            LL ans = phi(a0);
            int id = 0;
            devide(ans,id);
            for(int i=0; i<id; i++)
            {
                for(int j=0; j<e[i][1]; j++)
                {
                    if(pow_mod(X,ans/e[i][0],a0)==1) ans/=e[i][0]; ///分解本身，得到 X^ans % a0 = 1的最小ans
                }
            }
            printf("%lld
",ans);
        }
    }
    return 0;
}