hdu-3307 (欧拉定理+推导)

傷城~ 2022-06-10 13:38 142阅读 0赞

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** = 0.

Input

Each line will contain only three integers X, Y, a 0 ( 1 < X < 2 31, 0 <= Y < 2 63, 0 < a 0 < 2 31).

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

题目题意：题目给你三个数x,y,a0 ,我们知道了一个等式，an=x\*an-1+y 并且y mod x-1 ==0 让我们求一个最小的k使得ak % a0 =0.

题目分析：我们首先对那个等式变一下形，高中数列基础比较好的话，对这样的式子比较敏感的。

比较简单，为了方便，下面简单写了一下:

![Center][]  
得到了这个式子，我们的题目是要让它为0，我们取B与a0的最大公约数gcd(B,a0),那么我们可以得到(x^n-1)\*b%a0等价为(x^n-1)\*(b%gcd)%(a0%gcd)因为（b%gcd)%(a0%gcd)肯定不会为0了，它们的最大公约数都没又来，不能在约了，所以要使得等式为0，只有使得(x^n-1)%(a0%gcd)==0,我们变一下形：

x^n-1=k\*(a0%gcd)

x^n=k\*(a0%gcd)+1

左右模a0%gcd

即 x^n=1%(a0%gcd)

这个式子已经满足欧拉定理形式了。

在 [数论][Link 1] 中， 欧拉定理, （也称 [费马][Link 2] \-欧拉定理 ）是一个关于同余的性质。欧拉定理表明，若n,a为 [正整数][Link 3] ，且n,a [互质][Link 4] ，则: ![0823dd54564e92584b7cba389d82d158cdbf4e9f.jpg][]

题目要找是最小的，那么就是phi\[n\]的因子。

代码如下:

#include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<cstring>
    #define ll long long
    using namespace std;
    
    const int maxn=1e6+10;
    int prime[maxn],cnt;
    bool vis[maxn];
    void get_prime()//素数打表
    {
        memset (vis,true,sizeof (vis));
        vis[1]=false;
        for (int i=2;i<maxn;i++) {
            if (vis[i]) prime[cnt++]=i;
            for (int j=i;j<cnt&&i*prime[j]<maxn;j++) {
                vis[i*prime[j]]=false;
                if (i%prime[j]==0) break;
            }
        }
    }
    
    ll gcd (ll a,ll b)
    {
         if (b==0) return a;
         return gcd(b,a%b);
    }
    
    ll factor[100][2],fcnt;
    void get_factor(ll n)//质因子分解
    {
        memset (factor,0,sizeof (factor));
        fcnt=0;
        for (int i=0;i<cnt&&prime[i]*prime[i]<=n;i++) {
            if (n%prime[i]==0) {
                factor[fcnt][0]=prime[i];
                while (n%prime[i]==0) {
                    factor[fcnt][1]++;
                    n=n/prime[i];
                }
                fcnt++;
            }
        }
        if (n!=1) {
            factor[fcnt][0]=n;
            factor[fcnt++][1]=1;
        }
    }
    
    ll fast_pow(ll base,ll k,ll mod)//快速幂
    {
        ll ans=1;
        while (k) {
            if (k&1)
                ans=ans*base%mod;
            base=base*base%mod;
            k>>=1;
        }
        return ans;
    }
    ll get_euler(ll n)
    {
        ll res=n,a=n;
        for (ll i=2;i*i<=n;i++) {
            if (a%i==0) {
                res=res/i*(i-1);
                while (a%i==0) a=a/i;
            }
        }
        if (a>1)
           res=res/a*(a-1);
        return res;
    }
    
    int main()
    {
        get_prime();
        ll x,y,a;
        while (scanf("%lld%lld%lld",&x,&y,&a)!=EOF) {
            y=y/(x-1);
            ll gc=gcd (y,a);
            a=a/gc;
            if (gcd (a,x)!=1) {//不满足欧拉定理
                printf("Impossible!\n");
                continue;
            }
            ll phi=get_euler(a),ans;
            get_factor(phi);
            ans=phi;
            for (int i=0;i<fcnt;i++) {
                for (int j=0;j<factor[i][1];j++) {//把可以去掉的因子都去了，
                    if (fast_pow(x,ans/factor[i][0],a)==1) ans=ans/factor[i][0];
                }
            }
            printf("%lld\n",ans);
        }
        return 0;
    }

[Center]: /images/20220610/879597828bdd4402b7c1cc9becac90d0.png
[Link 1]: https://baike.baidu.com/item/%E6%95%B0%E8%AE%BA
[Link 2]: https://baike.baidu.com/item/%E8%B4%B9%E9%A9%AC
[Link 3]: https://baike.baidu.com/item/%E6%AD%A3%E6%95%B4%E6%95%B0
[Link 4]: https://baike.baidu.com/item/%E4%BA%92%E8%B4%A8
[0823dd54564e92584b7cba389d82d158cdbf4e9f.jpg]: https://gss2.bdstatic.com/9fo3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D116/sign=b4a8aa2a7dd98d1072d40830173eb807/0823dd54564e92584b7cba389d82d158cdbf4e9f.jpg