题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3307

Description has only two Sentences

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

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

a_n = X*a_n-1 + Y ，给你X,Y,a₀，叫你求出最小的整数k(k>0)使得 a_k% a₀=0。根据公式我们可以求出a_n= a₀*X^n-1+(x⁰+x¹+x²+……+x^n-1)Y。由等比数列前项和公式可得

a_n=a₀*X^n-1+(xⁿ-1)*Y/(x-1)。

所以只需令(x^k-1)*Y/(x-1)%a₀=0，求出k的值。

令Y'=Y/(x-1),d=gcd(Y/(x-1),a₀)

Y'/=d,a₀/=d;

此时Y'与a₀互质

(x^k-1)*Y/(x-1)%a₀=0

等价于

(x^k-1)%a₀=0

x^k%a₀=1

而这就符合欧拉定理a^φ(n)Ξ 1(mod n)

x^φ(a₀)Ξ 1(mod a₀)

如果gcd(x,a₀)!=1则k无解

否则k为phi(a₀)除以满足条件的phi(a₀)的因子

#include<iostream>

using namespace std;

#define ll long long

ll zys[][],cnt;

ll gcd(ll a,ll b)

{

    return b?gcd(b,a%b):a;

}

ll phi(ll x)

{

    ll ans=x;

    for(ll i=;i*i<=x;i++)

    {

        if(x%i==)

        {

            ans=ans/i*(i-);

            while(x%i==)x/=i;

        }

    }

    if(x>)

    ans=ans/x*(x-);

    return ans;

}

void fj(ll ans)

{

    for(ll i=;i*i<=ans;i++)

    {

        if(ans%i==)

        {

            zys[cnt][]=i;

            zys[cnt][]=;

            while(ans%i==)

            {

                ans/=i;

                zys[cnt][]++;

            }

            cnt++;

        }

    }

    if(ans>)

    {

        zys[cnt][]=ans;

        zys[cnt++][]=;

    }

}

ll poww(ll a,ll b,ll mod)

{

    ll ans=;

    while(b)

    {

        if(b&)ans=ans*a%mod;

        a=a*a%mod;

        b>>=;

    }

    return ans;

}

int main()

{

    ll x,y,a,c,d;

    while(cin>>x>>y>>a)

    {

        if(x==)

        {

            if(gcd(y,a)==)cout<<a<<endl;

            else cout<<a/gcd(y,a);

            continue;

        }

        c=y/(x-);

        if(c%a==)

        {

            cout<<<<endl;

            continue;

        }

        d=gcd(c,a);

        if(gcd(x,a/d)!=)cout<<"Impossible!"<<endl;

        else

        {

            a/=d;

            ll ans=phi(a);

            cnt=;

            fj(ans);

            for(int i=;i<cnt;i++)

            {

                for(int j=;j<=zys[i][];j++)

                {

                    if(poww(x,ans/zys[i][],a)==)ans/=zys[i][];

                }

            }

            cout<<ans<<endl;

        }

    }

    return ;

}

巴特西

hdu3307 欧拉函数

Description has only two Sentences

最新文章

热门文章