首页 > 代码库 > 【BZOJ 1319】 Sgu261Discrete Rootsv (原根+BSGS+EXGCD)
【BZOJ 1319】 Sgu261Discrete Rootsv (原根+BSGS+EXGCD)
1319: Sgu261Discrete Roots
Time Limit: 1 Sec Memory Limit: 64 MB
Submit: 389 Solved: 172Description
给出三个整数p,k,a,其中p为质数，求出所有满足x^k=a (mod p),0<=x<=p-1的x。Input
三个整数p,k,a。Output
第一行一个整数，表示符合条件的x的个数。 第二行开始每行一个数，表示符合条件的x,按从小到大的顺序输出。Sample Input
11 3 8Sample Output
1
2HINT
2<=p<p<=10^9
2<=k<=100000,0<=a
【分析】
终于发现原根的用处了！原根的幂构成模p的缩系，即用原根的幂可以表示所有模p下的数。假设模p下的一个原根是g，对于方程x^k=a(%prim) 可以写成(g^i)^k三g^j(%p),那么有g^j=三a（mod p），j可以用BSGS求得，那么i*k三j(%phi[p])，这个可以用exgcd求出所有可行的i，答案为g^i。
代码如下：
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 #include<algorithm> 6 #include<queue> 7 #include<cmath> 8 using namespace std; 9 #define LL long long 10 #define Maxn 1000010 11 12 LL ax,ay; 13 LL exgcd(LL a,LL b) 14 { 15 if(b==0) {ax=1;ay=0;return a;} 16 LL g=exgcd(b,a%b); 17 LL xx=ax; 18 ax=ay;ay=xx-(a/b)*ay; 19 return g; 20 } 21 22 LL np[Maxn]; 23 void div(LL x) 24 { 25 np[0]=0; 26 for(LL i=2;i*i<=x;i++) if(x%i==0) 27 { 28 np[++np[0]]=i; 29 while(x%i==0) x/=i; 30 } 31 if(x>1) np[++np[0]]=x; 32 } 33 34 LL qpow(LL x,LL b,LL p) 35 { 36 LL xx=x,pp=p,ans=1; 37 while(b) 38 { 39 if(b&1) ans=(ans*xx)%p; 40 xx=(xx*xx)%p; 41 b>>=1; 42 } 43 return (LL)ans; 44 } 45 46 LL ffind(LL p) 47 { 48 div(p-1); 49 for(LL i=2;i<p;i++) 50 { 51 bool ok=1; 52 for(LL j=1;j<=np[0];j++) 53 { 54 if(qpow(i,(p-1)/np[j],p)==1) {ok=0;break;} 55 } 56 if(ok) return i; 57 } 58 return -1; 59 } 60 61 LL cnt; 62 struct node 63 { 64 LL id,val; 65 }t[Maxn]; 66 67 bool cmp(node x,node y) {return (x.val==y.val)?(x.id<y.id):(x.val<y.val);} 68 69 LL t_div(LL x) 70 { 71 LL l=0,r=cnt; 72 while(l<r) 73 { 74 LL mid=(l+r)>>1; 75 if(t[mid].val==x) return t[mid].id; 76 if(t[mid].val>x) r=mid-1; 77 else l=mid+1; 78 } 79 if(t[l].val==x) return t[l].id; 80 return -1; 81 } 82 83 LL BSGS(LL x,LL c,LL p) 84 { 85 t[0].id=0;t[0].val=1; 86 LL sq=(LL)ceil(sqrt((double)p)); 87 for(LL i=1;i<=sq;i++) t[i].id=i,t[i].val=(t[i-1].val*x)%p; 88 sort(t,t+1+sq,cmp); 89 cnt=0; 90 for(LL i=1;i<=sq;i++) if(t[i].val!=t[i-1].val) t[++cnt]=t[i]; 91 92 LL bm=qpow(x,sq,p); 93 bm=qpow(bm,p-2,p); 94 LL tmp=c; 95 for(LL i=0;i<=sq;i++) 96 { 97 LL now=t_div(tmp); 98 if(now!=-1) return i*sq+now; 99 tmp=(tmp*bm)%p;100 }101 return -1;102 }103 104 LL op[Maxn];105 106 int main()107 {108 LL p,k,a;109 scanf("%lld%lld%lld",&p,&k,&a);110 LL g=ffind(p);111 LL C=BSGS(g,a,p);112 if(C==-1) {printf("0\n");return 0;}113 C%=p-1;114 LL d=exgcd(k,p-1);115 if(C%d!=0) {printf("0\n");return 0;}116 ax*=C/d; 117 ax=(ax%((p-1)/d)+((p-1)/d))%((p-1)/d);118 119 LL ans=qpow(g,ax,p),id=ax,mx=ans,add=qpow(g,(p-1)/d,p);120 op[0]=0;121 op[++op[0]]=ans;122 LL fs=ans;123 while(add!=1)124 {125 id=ax+((p-1)/d);126 ans=(ans*add)%p;127 if(ans==fs) break;128 op[++op[0]]=ans;129 }130 sort(op+1,op+1+op[0]);131 printf("%lld\n",op[0]);132 for(LL i=1;i<=op[0];i++) printf("%lld\n",op[i]);133 return 0;134 }
2016-09-07 13:52:58
【BZOJ 1319】 Sgu261Discrete Rootsv (原根+BSGS+EXGCD)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。