【POJ 3243-Clever Y】与【POJ 2417-Discrete Logging】（解高次同余方程 Baby-Step-Gaint-Step）

太过爱你忘了你带给我的痛 2022-09-24 15:25 61阅读 0赞

Clever Y

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;5000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;65536K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;7969</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;1986</td> 
  </tr> 
 </tbody> 
</table>

Description

Little Y finds there is a very interesting formula in mathematics:

*XY mod Z = K*

Given *X*, *Y*, *Z*, we all know how to figure out *K* fast. However, given *X*, *Z*, *K*, could you figure out *Y* fast?

Input

Input data consists of no more than 20 test cases. For each test case, there would be only one line containing 3 integers *X*, *Z*, *K* (0 ≤ *X*, *Z*, *K* ≤ 10 9).  
Input file ends with 3 zeros separated by spaces.

Output

For each test case output one line. Write "No Solution" (without quotes) if you cannot find a feasible *Y* (0 ≤ *Y* < *Z*). Otherwise output the minimum *Y* you find.

Sample Input

5 58 33
    2 4 3
    0 0 0

Sample Output

9
    No Solution

Source

[POJ Monthly--2007.07.08][], Guo, Huayang

## 题目意思： ##

已知X，Z和K，求解Y满足： (X^Y) mod Z=K，即  (X^Y)≡K(mod Z)。

## 解题思路： ##

模板题，解高次同余方程。

#include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<cmath>
    #include<malloc.h>
    using namespace std;
    typedef long long ll;
    #define maxn 100000
    
    struct Hash
    {
        int a,b,next;
    } hash[2*maxn];
    int flag[maxn];
    int top,idx;
    
    void ins(int a,int b)
    {
        int k=b&maxn;
        if(flag[k]!=idx)
        {
            flag[k]=idx;
            hash[k].next=-1;
            hash[k].a=a;
            hash[k].b=b;
            return;
        }
        while(hash[k].next!=-1)
        {
            if(hash[k].b==b) return;
            k=hash[k].next;
        }
        hash[k].next=++top;
        hash[top].next=-1;
        hash[top].a=a;
        hash[top].b=b;
    }
    
    int find(int b)
    {
        int k=b&maxn;
        if(flag[k]!=idx) return -1;
        while(k!=-1)
        {
            if(hash[k].b==b) return hash[k].a;
            k=hash[k].next;
        }
        return -1;
    }
    
    int gcd(int a,int b)
    {
        return b==0?a:gcd(b,a%b);
    }
    
    int exgcd(int a,int b,int &x,int &y)
    {
        int t,d;
        if(!b)
        {
            x=1,y=0;
            return a;
        }
        d=exgcd(b,a%b,x,y);
        t=x,x=y,y=t-a/b*y;
        return d;
    }
    
    int inval(int a,int b,int n)
    {
        int x,y,e;
        exgcd(a,n,x,y);
        e=(long long)x*b%n;
        return e<0?e+n:e;
    }
    
    int pow_mod(long long a,int b,int c)
    {
        long long ret=1%c;
        a%=c;
        while(b)
        {
            if(b&1) ret=ret*a%c;
            a=a*a%c;
            b>>=1;
        }
        return ret;
    }
    
    int BabyStep(int A,int B,int C)
    {
        top=maxn;
        ++idx;
        long long buf=1%C,D=buf,K;
        int i,d=0,tmp;
        for(i=0; i<=100; buf=buf*A%C,++i)
            if(buf==B) return i;
        while((tmp=gcd(A,C))!=1)
        {
            if(B%tmp) return -1;
            ++d;
            C/=tmp;
            B/=tmp;
            D=D*A/tmp%C;
        }
        int M=(int)ceil(sqrt((double)C));
        for(buf=1%C,i=0; i<=M; buf=buf*A%C,++i)
            ins(i,buf);
        for(i=0,K=pow_mod((long long)A,M,C); i<=M; D=D*K%C,++i)
        {
            tmp=inval((int)D,B,C);
            int w;
            if(tmp>=0&&(w=find(tmp))!=-1)
                return i*M+w+d;
        }
        return -1;
    }
    
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        int A,B,C;
        while(cin>>A>>C>>B,A||B||C)
        {
            B%=C;
            int tmp=BabyStep(A,B,C);
            if(tmp<0) puts("No Solution");
            else cout<<tmp<<endl;
        }
        return 0;
    }
    /**
    5 58 33
    2 4 3
    0 0 0
    **/

Discrete Logging

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;5000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;65536K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;5064</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;2301</td> 
  </tr> 
 </tbody> 
</table>

Description

Given a prime P, 2 <= P < 2 31, an integer B, 2 <= B < P, and an integer N, 1 <= N < P, compute the discrete logarithm of N, base B, modulo P. That is, find an integer L such that

BL == N (mod P)

Input

Read several lines of input, each containing P,B,N separated by a space.

Output

For each line print the logarithm on a separate line. If there are several, print the smallest; if there is none, print "no solution".

Sample Input

5 2 1
    5 2 2
    5 2 3
    5 2 4
    5 3 1
    5 3 2
    5 3 3
    5 3 4
    5 4 1
    5 4 2
    5 4 3
    5 4 4
    12345701 2 1111111
    1111111121 65537 1111111111

Sample Output

0
    1
    3
    2
    0
    3
    1
    2
    0
    no solution
    no solution
    1
    9584351
    462803587

Hint

The solution to this problem requires a well known result in number theory that is probably expected of you for Putnam but not ACM competitions. It is Fermat's theorem that states

B(P-1) == 1 (mod P)

for any prime P and some other (fairly rare) numbers known as base-B pseudoprimes. A rarer subset of the base-B pseudoprimes, known as Carmichael numbers, are pseudoprimes for every base between 2 and P-1. A corollary to Fermat's theorem is that for any m

B(-m) == B(P-1-m) (mod P) .

Source

[Waterloo Local 2002.01.26][]

#include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<cmath>
    #include<malloc.h>
    using namespace std;
    typedef long long ll;
    #define maxn 65535//这里写大于65535的数会WA
    
    struct Hash
    {
        ll a,b,next;
    } hash[2*maxn];
    ll flag[maxn];
    ll top,idx;
    
    void ins(ll a,ll b)
    {
        ll k=b&maxn;
        if(flag[k]!=idx)
        {
            flag[k]=idx;
            hash[k].next=-1;
            hash[k].a=a;
            hash[k].b=b;
            return;
        }
        while(hash[k].next!=-1)
        {
            if(hash[k].b==b) return;
            k=hash[k].next;
        }
        hash[k].next=++top;
        hash[top].next=-1;
        hash[top].a=a;
        hash[top].b=b;
    }
    
    ll find(ll b)
    {
        ll k=b&maxn;
        if(flag[k]!=idx) return -1;
        while(k!=-1)
        {
            if(hash[k].b==b) return hash[k].a;
            k=hash[k].next;
        }
        return -1;
    }
    
    ll gcd(ll a,ll b)
    {
        return b==0?a:gcd(b,a%b);
    }
    
    ll exgcd(ll a,ll b,ll &x,ll &y)
    {
        ll t,d;
        if(!b)
        {
            x=1,y=0;
            return a;
        }
        d=exgcd(b,a%b,x,y);
        t=x,x=y,y=t-a/b*y;
        return d;
    }
    
    ll inval(ll a,ll b,ll n)
    {
        ll x,y,e;
        exgcd(a,n,x,y);
        e=(long long)x*b%n;
        return e<0?e+n:e;
    }
    
    ll pow_mod(long long a,ll b,ll c)
    {
        long long ret=1%c;
        a%=c;
        while(b)
        {
            if(b&1) ret=ret*a%c;
            a=a*a%c;
            b>>=1;
        }
        return ret;
    }
    
    ll BabyStep(ll A,ll B,ll C)
    {
        top=maxn;
        ++idx;
        long long buf=1%C,D=buf,K;
        ll i,d=0,tmp;
        for(i=0; i<=100; buf=buf*A%C,++i)
            if(buf==B) return i;
        while((tmp=gcd(A,C))!=1)
        {
            if(B%tmp) return -1;
            ++d;
            C/=tmp;
            B/=tmp;
            D=D*A/tmp%C;
        }
        ll M=(ll)ceil(sqrt((double)C));
        for(buf=1%C,i=0; i<=M; buf=buf*A%C,++i)
            ins(i,buf);
        for(i=0,K=pow_mod((long long)A,M,C); i<=M; D=D*K%C,++i)
        {
            tmp=inval((ll)D,B,C);
            ll w;
            if(tmp>=0&&(w=find(tmp))!=-1)
                return i*M+w+d;
        }
        return -1;
    }
    
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        ll A,B,C;
        while(cin>>C>>A>>B)
        {
            B%=C;
            ll tmp=BabyStep(A,B,C);
            if(tmp<0) puts("no solution");
            else cout<<tmp<<endl;
        }
        return 0;
    }
    
    /**
    5 2 1
    5 2 2
    5 2 3
    5 2 4
    5 3 1
    5 3 2
    5 3 3
    5 3 4
    5 4 1
    5 4 2
    5 4 3
    5 4 4
    12345701 2 1111111
    1111111121 65537 1111111111
    **/

[POJ Monthly--2007.07.08]: http://poj.org/searchproblem?field=source&key=POJ+Monthly--2007.07.08
[Waterloo Local 2002.01.26]: http://poj.org/searchproblem?field=source&key=Waterloo+Local+2002.01.26