本文共 4285 字，大约阅读时间需要 14 分钟。
今天研究了一下这块内容...首先是板子
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define pb push_back#define mp make_pairtypedef pair pii;typedef long long ll;typedef double ld;typedef vector vi;#define fi first#define se second#define fe first#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}#define Edg int M=0,fst[SZ],vb[SZ],nxt[SZ];void ad_de(int a,int b){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;}void adde(int a,int b){ad_de(a,b);ad_de(b,a);}#define Edgc int M=0,fst[SZ],vb[SZ],nxt[SZ],vc[SZ];void ad_de(int a,int b,int c){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;vc[M]=c;}void adde(int a,int b,int c){ad_de(a,b,c);ad_de(b,a,c);}#define es(x,e) (int e=fst[x];e;e=nxt[e])#define esb(x,e,b) (int e=fst[x],b=vb[e];e;e=nxt[e],b=vb[e])#define VIZ {printf("digraph G{\n"); for(int i=1;i<=n;i++) for es(i,e) printf("%d->%d;\n",i,vb[e]); puts("}");}#define VIZ2 {printf("graph G{\n"); for(int i=1;i<=n;i++) for es(i,e) if(vb[e]>=i)printf("%d--%d;\n",i,vb[e]); puts("}");}#define SZ 666666template inline T dw();template<>inline ll dw () { return 1;}template<>inline int dw () { return 1;}typedef pair pll;ll pll_s;inline pll mul(pll a,pll b,ll p){ pll ans; ans.fi=a.fi*b.fi%p+a.se*b.se%p*pll_s%p; ans.se=a.fi*b.se%p+a.se*b.fi%p; ans.fi%=p; ans.se%=p; return ans;}inline ll mul(ll a,ll b,ll c){ return a*b%c;}//a^b mod ctemplate T qp(T a,ll b,ll c){ T ans=dw (); while(b) { if(b&1) ans=mul(ans,a,c); a=mul(a,a,c); b>>=1; } return ans;}inline ll ll_rnd(){ ll ans=0; for(int i=1;i<=5;i++) ans=ans*32768+rand(); if(ans<0) ans=-ans; return ans;}//(x,y) -> x+sqrt(pll_s)*ytemplate<>inline pll dw () { return pll(1,0);}//find (possibly) one root of x^2 mod p=a//correctness need to be checkedll sqr(ll a,ll p){ if(!a) return 0; if(p==2) return 1; ll w,q; while(1) { w=ll_rnd()%p; q=w*w-a; q=(q%p+p)%p; if(qp(q,(p-1)/2,p)!=1) break; } pll_s=q; pll rst=qp(pll(w,1),(p+1)/2,p); ll ans=rst.fi; ans=(ans%p+p)%p; return ans;}//solve x^2 mod p=avector all_sqr(ll a,ll p){ vector vec; a=(a%p+p)%p; if(!a) {vec.pb(0); return vec;} ll g=sqr(a,p); ll g2=(p-g)%p; if(g>g2) swap(g,g2); if(g*g%p==a) vec.pb(g); if(g2*g2%p==a&&g!=g2) vec.pb(g2); return vec;}ll s3_a;//f0+f1*x+f2*x^2 (for x^3=s3_a)struct s3{ ll s[3]; s3() {s[0]=s[1]=s[2]=0;} s3(ll* p) {s[0]=p[0]; s[1]=p[1]; s[2]=p[2];} s3(ll a,ll b,ll c) {s[0]=a; s[1]=b; s[2]=c;}};template<>s3 dw () { return s3(1,0,0);}s3 rs3(ll p){ return s3(ll_rnd()%p,ll_rnd()%p,ll_rnd()%p);}s3 mul(s3 a,s3 b,ll p){ ll k[3]={}; for(int i=0;i<3;i++) { for(int j=0;j<3;j++) { if(i+j<3) k[i+j]+=a.s[i]*b.s[j]%p; else k[i+j-3]+=a.s[i]*b.s[j]%p*s3_a%p; } } for(int i=0;i<3;i++) k[i]%=p; return s3(k[0],k[1],k[2]);}//solve x^3 mod p=avector all_cr(ll a,ll p){ vector vec; a=(a%p+p)%p; if(!a) {vec.pb(0); return vec;} if(p<=3) { for(int i=0;i gg;ll yss[2333]; int yyn=0;//find x's primitive rootinline ll org_root(ll x){ ll& pos=gg[x]; if(pos) return pos; yyn=0; ll xp=x-1; for(ll i=2;i*i<=xp;i++) { if(xp%i) continue; yss[++yyn]=i; while(xp%i==0) xp/=i; } if(xp!=1) yss[++yyn]=xp; ll ans=1; while(1) { bool ok=1; for(int i=1;i<=yyn;i++) { ll y=yss[i]; if(qp(ans,(x-1)/y,x)==1) {ok=0; break;} } if(ok) return pos=ans; ++ans; }}map bsgs_mp;//find smallest x: a^x mod p=bll bsgs(ll a,ll b,ll p){ if(b==0) return 1; map & ma=bsgs_mp; ma.clear(); //only /2.5 for speed... ll hf=sqrt(p)/2.5+2,cur=b; for(int i=0;i T gcd(T a,T b) { if(b) return gcd(b,a%b); return a;}//solve x^a mod p=bvector kr(ll a,ll b,ll p){ vector rst; if(!b) {rst.pb(0); return rst;} ll g=org_root(p); ll pb=bsgs(g,b,p); ll b1=a,b2=p-1,c=pb; ll gg=gcd(b1,b2); if(c%gg) return rst; b1/=gg, b2/=gg, c/=gg; ll x1,x2; exgcd(b1,b2,x1,x2); x1*=c; x1=(x1%b2+b2)%b2; ll cs=qp(g,x1,p),ec=qp(g,b2,p); for(ll cur=x1;cur
这份代码可以解决1014、1039、1038三道题。感人至深
参考链接是糖老师的这篇文章：
感觉二次和三次剩余里面已经讲得挺清楚了，注意三次剩余里面那个多项式群里面自变量取值是满足x^3=a的。
这里就讲一下k次剩余娱乐一下。
我们要解x^a mod p=b，p是个质数，那么p就有原根g。
考虑两边对原根g取log，设g^r=b，r可以用bsgs求出来，那么我们就是要求s*a mod (p-1)=r，那么x就等于g^s。
这个东西我们可以设s*a+qwq*(p-1)=r，先把(a,p-1)约分，用exgcd解出来一个s，然后就只要加上(约分后的p-1)的倍数就可以剩下的解了。
此外这题需要卡常，见bsgs函数里的/2.5。
转载于:https://www.cnblogs.com/zzqsblog/p/6259911.html