Time Limit: 5000MS | Memory Limit: 65536K | |
Total Submissions: 3696 | Accepted: 1727 |
Description
B
L
== N (mod P)
Input
Output
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
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
题意要求解一个 k^D = n ( mod p ) 的一个最小D
一开始也不会解 。
在网上看了一下,原来是用到一个 Baby step giant step 的算法 。
先要把 D 分解 , D = i * m + j ( m = ceil( sqrt (p - 1 ) ) )
原式 : k^D = n ( mod p )
-> k^i^m * k^j = n (mod p )
-> k^j = n * ( k ^(-m)^ i ) ( mod p )
根据题目给的 Hint ( 费马小定理 )可以求出 k^m 的逆元 .
然后枚举 i , 查找是否存在 k^j 与 n * ( k ^(-m)^i ) 相等
所以预处理 k^j ( mod p ) 排序以后 , 就可以进行二分查找了 (复杂度降为log(m))。
加上枚举 , 那么总复杂度就是 m*log(m) .
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long LL ;
const int N = ; struct B
{
LL num , id ;
bool operator < ( const B &a ) const{
if( num != a.num ) return num < a.num;
else return id < a.id ;
}
}baby[N]; LL n , k , p ;
int tot ; LL quick_mod( LL a , LL b ,LL mod )
{
LL res = ;
while( b )
{
if( b & ) res = res * a % mod ;
a = a * a % mod ;
b >>= ;
}
return res ;
}
int find( LL n )
{
int l = , r = tot - ;
while( l <= r ){
int m = (l + r) >> ;
if( baby[m].num == n){
return baby[m].id;
}
else if( baby[m].num < n )
l = m + ;
else
r = m - ;
}
return -;
}
void run()
{
int m = (int)ceil(sqrt((double)(p-)));
baby[].num = , baby[].id = ;
for( int i = ; i < m ; ++i ){
baby[i].id = i ;
baby[i].num = baby[i-].num * k % p ; // k^j
}
sort( baby , baby + m );
tot = ;
for( int i = ; i < m ; ++i ){
if( baby[tot-].num != baby[i].num ) baby[tot++] = baby[i];
} LL bm = quick_mod( k , p - - m , p ) ; // k^(-m) ;
LL temp = n ; for( int j = ; j < m ; ++j ){
// k^(-m)^j
int pos = find( temp );
if( pos != - ){
printf("%d\n" , ( m * j + pos ) );
return ;
}
temp = temp * bm % p ;
}
puts("no solution");
}
int main()
{
#ifdef LOCAL
freopen("in.txt","r",stdin);
#endif // LOCAL
while( ~scanf("%lld%lld%lld",&p,&k,&n) ) run();
}