2 条题解
-
0
终于发现原根的用处了！原根的幂构成模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。
#include <bits/stdc++.h> using namespace std; #define LL long long #define Maxn 1000010 LL ax,ay; LL exgcd(LL a,LL b) { if(b==0) {ax=1;ay=0;return a;} LL g=exgcd(b,a%b); LL xx=ax; ax=ay;ay=xx-(a/b)*ay; return g; } LL np[Maxn]; void div(LL x) { np[0]=0; for(LL i=2;i*i<=x;i++) if(x%i==0) { np[++np[0]]=i; while(x%i==0) x/=i; } if(x>1) np[++np[0]]=x; } LL qpow(LL x,LL b,LL p) { LL xx=x,pp=p,ans=1; while(b) { if(b&1) ans=(ans*xx)%p; xx=(xx*xx)%p; b>>=1; } return (LL)ans; } LL ffind(LL p) { div(p-1); for(LL i=2;i<p;i++) { bool ok=1; for(LL j=1;j<=np[0];j++) { if(qpow(i,(p-1)/np[j],p)==1) {ok=0;break;} } if(ok) return i; } return -1; } LL cnt; struct node { LL id,val; }t[Maxn]; bool cmp(node x,node y) {return (x.val==y.val)?(x.id<y.id):(x.val<y.val);} LL t_div(LL x) { LL l=0,r=cnt; while(l<r) { LL mid=(l+r)>>1; if(t[mid].val==x) return t[mid].id; if(t[mid].val>x) r=mid-1; else l=mid+1; } if(t[l].val==x) return t[l].id; return -1; } LL BSGS(LL x,LL c,LL p) { t[0].id=0;t[0].val=1; LL sq=(LL)ceil(sqrt((double)p)); for(LL i=1;i<=sq;i++) t[i].id=i,t[i].val=(t[i-1].val*x)%p; sort(t,t+1+sq,cmp); cnt=0; for(LL i=1;i<=sq;i++) if(t[i].val!=t[i-1].val) t[++cnt]=t[i]; LL bm=qpow(x,sq,p); bm=qpow(bm,p-2,p); LL tmp=c; for(LL i=0;i<=sq;i++) { LL now=t_div(tmp); if(now!=-1) return i*sq+now; tmp=(tmp*bm)%p; } return -1; } LL op[Maxn]; int main() { LL p,k,a; scanf("%lld%lld%lld",&p,&k,&a); LL g=ffind(p); LL C=BSGS(g,a,p); if(C==-1) {printf("0\n");return 0;} C%=p-1; LL d=exgcd(k,p-1); if(C%d!=0) {printf("0\n");return 0;} ax*=C/d; ax=(ax%((p-1)/d)+((p-1)/d))%((p-1)/d); LL ans=qpow(g,ax,p),id=ax,mx=ans,add=qpow(g,(p-1)/d,p); op[0]=0; op[++op[0]]=ans; LL fs=ans; while(add!=1) { id=ax+((p-1)/d); ans=(ans*add)%p; if(ans==fs) break; op[++op[0]]=ans; } sort(op+1,op+1+op[0]); printf("%lld\n",op[0]); for(LL i=1;i<=op[0];i++) printf("%lld\n",op[i]); return 0; } -
0
huangzheng
LV 6
@ 2025-10-8 17:03:28
/* 终于发现原根的用处了！原根的幂构成模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。 */ #include <bits/stdc++.h> using namespace std; #define LL long long #define Maxn 1000010 LL ax,ay; LL exgcd(LL a,LL b) { if(b==0) {ax=1;ay=0;return a;} LL g=exgcd(b,a%b); LL xx=ax; ax=ay;ay=xx-(a/b)*ay; return g; } LL np[Maxn]; void div(LL x) { np[0]=0; for(LL i=2;i*i<=x;i++) if(x%i==0) { np[++np[0]]=i; while(x%i==0) x/=i; } if(x>1) np[++np[0]]=x; } LL qpow(LL x,LL b,LL p) { LL xx=x,pp=p,ans=1; while(b) { if(b&1) ans=(ans*xx)%p; xx=(xx*xx)%p; b>>=1; } return (LL)ans; } LL ffind(LL p) { div(p-1); for(LL i=2;i<p;i++) { bool ok=1; for(LL j=1;j<=np[0];j++) { if(qpow(i,(p-1)/np[j],p)==1) {ok=0;break;} } if(ok) return i; } return -1; } LL cnt; struct node { LL id,val; }t[Maxn]; bool cmp(node x,node y) {return (x.val==y.val)?(x.id<y.id):(x.val<y.val);} LL t_div(LL x) { LL l=0,r=cnt; while(l<r) { LL mid=(l+r)>>1; if(t[mid].val==x) return t[mid].id; if(t[mid].val>x) r=mid-1; else l=mid+1; } if(t[l].val==x) return t[l].id; return -1; } LL BSGS(LL x,LL c,LL p) { t[0].id=0;t[0].val=1; LL sq=(LL)ceil(sqrt((double)p)); for(LL i=1;i<=sq;i++) t[i].id=i,t[i].val=(t[i-1].val*x)%p; sort(t,t+1+sq,cmp); cnt=0; for(LL i=1;i<=sq;i++) if(t[i].val!=t[i-1].val) t[++cnt]=t[i]; LL bm=qpow(x,sq,p); bm=qpow(bm,p-2,p); LL tmp=c; for(LL i=0;i<=sq;i++) { LL now=t_div(tmp); if(now!=-1) return i*sq+now; tmp=(tmp*bm)%p; } return -1; } LL op[Maxn]; int main() { LL p,k,a; scanf("%lld%lld%lld",&p,&k,&a); LL g=ffind(p); LL C=BSGS(g,a,p); if(C==-1) {printf("0\n");return 0;} C%=p-1; LL d=exgcd(k,p-1); if(C%d!=0) {printf("0\n");return 0;} ax*=C/d; ax=(ax%((p-1)/d)+((p-1)/d))%((p-1)/d); LL ans=qpow(g,ax,p),id=ax,mx=ans,add=qpow(g,(p-1)/d,p); op[0]=0; op[++op[0]]=ans; LL fs=ans; while(add!=1) { id=ax+((p-1)/d); ans=(ans*add)%p; if(ans==fs) break; op[++op[0]]=ans; } sort(op+1,op+1+op[0]); printf("%lld\n",op[0]); for(LL i=1;i<=op[0];i++) printf("%lld\n",op[i]); return 0; }
- 1
