前几天写了这道题，用了三个比较简单的模板，然后套在一起就没有然后了
题意如下：
给你两个质数p,k，和整数a(0≤a<p)，求解所有满足x^k≡a(mod p)的x。
至于解题分析嘛，目前我还不知道为啥我的blog打latex公式没有用，所以，我觉得下面链接那份份比我分析的好多了（懒啊
可以去这个看看哦https://www.cnblogs.com/w007878/p/3621653.html
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 |
#include <bits/stdc++.h> using namespace std; vector<long long> a; long long qpow(long long a,long long b,long long p) { long long res=1; while(b) { if (b&1) res=res*a%p; a=a*a%p; b/=2; } return res; } bool g_test(long long g,long long p) { for (long long i=0;i<a.size();i++) { if (qpow(g,(p-1)/a[i],p)==1) return 0; } return 1; } long long primitive_root(long long p) { long long tmp=p-1; for (long long i=2;i<=tmp/i;i++) { if (tmp%i==0) { a.push_back(i); while(tmp%i==0) { tmp/=i; } } } if (tmp!=1){ a.push_back(tmp); } long long g=1; while(true) { if (g_test(g,p)) return g; g++; } } long long extend_gcd(long long a,long long b,long long &x,long long &y) { if (b==0) { x=1;y=0; return a; } else { long long r=extend_gcd(b,a%b,y,x); y-=x*(a/b); return r; } } long long inv(long long a,long long p) { return qpow(a,p-2,p); } map<long long,long long> Map; long long getj(long long a,long long b,long long p) { long long l = sqrt(p-1), ret; for(int i = 0, j = 1; i < l; ++i) { Map[j] = i; j = (long long)j*a%p; } long long ia = qpow(inv(a, p), l, p), ta = 1; for(int k = 0, lim = (p-2)/l; k <= lim; ++k) { if(Map.find(b*ta%p) != Map.end()) { ret = k*l+Map[(long long)b*ta%p]; break; } ta = (long long)ta*ia%p; } return ret; } vector<long long> line_mod_equaliton(long long a,long long b,long long n) { long long x,y; long long d=extend_gcd(a,n,x,y); vector<long long> ans; ans.clear(); if (b%d==0) { x%=n;x+=n;x%=n; ans.push_back((x*(b/d)%(n/d))); for (long long i=1;i<d;i++) { ans.push_back((ans[0]+i*n/d)%n); } } return ans; } vector<long long> ans; int main() { long long p,k,a; while(~scanf("%lld%lld%lld",&p,&k,&a)) { if (a==0) { puts("1"); puts("0"); continue; } long long g=primitive_root(p); long long ja=getj(g,a,p); ans=line_mod_equaliton(k,ja,p-1); printf("%d\n",ans.size()); for (int i=0;i<ans.size();i++) { ans[i]=qpow(g,ans[i],p); } sort(ans.begin(),ans.end()); for (int i=0;i<ans.size();i++) { printf("%lld%c",ans[i]," \n"[i==ans.size()-1]); } } return 0; } |
