HDU 3307 Description has only two Sentences 数论

Description has only two Sentences

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

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_kmod 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!".

SampleInput

2 0 9

SampleOutput

1

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int d[1000000];
typedef long long  ll;
ll euler(ll n)
{
    ll i,ans = n,t = n;
    for( i = 2 ; i * i <= n ;i++ )
        if( t%i == 0) {
            ans -= ans/i;
            while( t%i == 0) t /= i;
        }
    if( t > 1) ans -= ans/t;
    return ans; 
}

ll gcd(ll a,ll b)
{
    return b?gcd(b, a%b):a;
}
ll fast_pow(ll a,ll b,ll c)     //a^b%c
{
    ll tmp=a%c,res=1;
    while (b) {
        if(b&1) res =res*tmp%c;
        tmp=tmp*tmp%c;
        b>>=1;
    }
    return res;
}
int main()
{
    ll x,y,a;
    while (cin>>x>>y>>a) {
        ll k=y/(x-1);
        if(k==0)    {cout<<"1"<<endl;continue;}//这儿也可以不特判，写的时候是因为快速幂写错WA了以后乱加的<img alt="难过" src="http://static.blog.csdn.net/xheditor/xheditor_emot/default/sad.gif">
        ll tmp=gcd(a,k);
        if(gcd(a/tmp, x)!=1){ cout<<"Impossible!"<<endl;continue;};
        ll res=euler(a/tmp),cnt=0;
        for(int i=1;i*i<=res;i++)
        {
            if(res%i==0)
            {
                d[cnt++]=i;
                if(res/i!=i)d[cnt++]=res/i;
            }
        }
        sort(d,d+cnt);
        for(int i=0;i<cnt;i++)
        {
            if(fast_pow(x, d[i],a/tmp)==1)
            {
                cout<<d[i]<<endl;
                break;
            }
        }
    }
    return 0;
}	

（x^k-1）*(y/(x-1))=0(mod a0)，再将（y/(x-1)）和a0先消掉公因数，就是要求最小k满足x^k=1(mod m)

k^euler(m)=1(modm),找euler(m)的因数中能满足k^x=1(mod m)的最小x(快速幂)

循环节：a^b=a^(b+t) (mod c) -> a^t=1(mod c) -> 满足a^x=1(mod c) 则 x=t*k;(抽屉原理)
euler: a^euler=1(mod c)

好像也可以用什么离散对数做，反正我不知道那东东