登 录
/* a ^ x = n (mod p) 计算x,该代码仅解决p为素数 */ #include <string.h> #include <stdio.h> #include <math.h> #include <algorithm> #include <iostream> using namespace std; typedef struct { int res, times; } rem; typedef __int64 LL; rem r[1000001]; bool cmp(rem r1 , rem r2) { if (r1.res == r2.res) return r1.times < r2.times; return r1.res < r2.res; } int binary(int x , int e) { int s = 0 , mid , ans = -1; while (s <= e) { mid = (s + e) >> 1; if (r[mid].res > x) e = mid - 1; else s = mid + 1; if (r[mid].res == x) ans = r[mid].times; } return ans; } int power(LL a,int b,int p) { LL ans = 1; while (b) { while (!(b&1)) { b >>= 1; a = a * a % p; } b --; ans = ans * a % p; } return ans; } int main() { int i , j , n , m , sq , p , a , asq , tmp; while (scanf("%d%d%d" , &a , &p , &n)!= EOF) { a %= p; n %= p; sq = (int)ceil(sqrt(double(p))); j = n; r[0].res = n; r[0].times = 0; for (i = 1;i <= sq;i ++) { j = (LL)j * a % p; r[i].res = j; r[i].times = i; } sort(r , r + sq + 1 , cmp); asq = power(a , sq , p); j = 1; for (i = 1;i <= sq;i ++) { j = (LL)j * asq % p; tmp = binary(j , sq); if (tmp + 1) break; } if (i > sq) printf("NONE/n"); else printf("%d/n" , i * sq - tmp); } return 0; }
抱歉!评论已关闭.