Discrete Logging

亦凉 2021-05-03 02:27 362阅读 0赞

Discrete Logging

| **Time Limit:** 5000MS      | **Memory Limit:** 65536K |                    |
| --------------------------- | ------------------------ | ------------------ |
| **Total Submissions:** 5865 |                          | **Accepted:** 2618 |

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

== 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

(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

(-m)

== B

(P-1-m)

(mod P) .

Source

BSGS模板题

#include<iostream>
     #include<cstdio>
     #include<cstring>
     #include<cmath>
     #include<map>
     #define LL long long 
     using namespace std;
     LL a,b,c;
     map<LL,LL>mp;
     LL fastpow(LL a,LL p,LL c)
     {
         LL base=a;LL ans=1;
         while(p!=0)
         {
             if(p%2==1)ans=(ans*base)%c;
             base=(base*base)%c;
             p=p/2;
         }
         return ans;
     }
     int main()
     {
         // a^x = b (mod c)
         while(scanf("%lld%lld%lld",&c,&a,&b)!=EOF)
         {
             LL m=ceil(sqrt(c));// 注意要向上取整 
             mp.clear();
             if(a%c==0)
             {
             printf("no solution\n");
             continue;
             }
             // 费马小定理的有解条件 
             LL ans;//储存每一次枚举的结果 b* a^j
             for(LL j=0;j<=m;j++)  // a^(i*m) = b * a^j
             {
                 if(j==0)
                 {
                     ans=b%c;
                     mp[ans]=j;// 处理 a^0 = 1 
                     continue;
                 }
                 ans=(ans*a)%c;// a^j 
                 mp[ans]=j;// 储存每一次枚举的结果 
             }
             LL t=fastpow(a,m,c);
             ans=1;//a ^(i*m)
             LL flag=0;
             for(LL i=1;i<=m;i++)
             {
                 ans=(ans*t)%c;
                 if(mp[ans])
                 {
                     LL out=i*m-mp[ans];// x= i*m-j
                     printf("%lld\n",(out%c+c)%c);
                     flag=1;
                     break;
                 }
                 
             }
             if(!flag)
             printf("no solution\n");    
         }
         
         return 0;
     }