数论模板总结

2019-04-13 20:56发布

站内文章 / 模拟电子
9724 0 1404
1.离散对数

ax≡b(modp)那么x≡loga（b)(modp)
那么现在我们就来求解这个x.
朴素baby step giant step要求p必须为质数.
整体的复杂度为O(n√)). //Hash + 扩展欧几里得 +拆分思想 /* 求解模方程a^x=b(mod n)，n为素数。 模板题。 时间复杂度O(sqrt(n)*logn) */ #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; //baby_step giant_step // a^x = b (mod n) n为素数，a,b < n // 求解上式 0<=x < n的解 #define MOD 76543 int hs[MOD],head[MOD],next[MOD],id[MOD],top; //Hash void insert(int x,int y) { int k = x%MOD; hs[top] = x, id[top] = y, next[top] = head[k], head[k] = top++; } int find(int x) { int k = x%MOD; for(int i = head[k]; i != -1; i = next[i]) if(hs[i] == x) return id[i]; return -1; } //baby step giant step int BSGS(int a,int b,int n) { memset(head,-1,sizeof(head)); top = 1; if(b == 1)return 0; int m = sqrt(n*1.0), j; long long x = 1, p = 1; for(int i = 0; i < m; ++i, p = p*a%n)insert(p*b%n,i); for(long long i = m; ;i += m) { if( (j = find(x = x*p%n)) != -1 )return i-j; if(i > n)break; } return -1; } int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); int a,b,n; // B ^ L = N (mod P) while(scanf("%d%d%d",&n,&a,&b) == 3)// P B N { int ans = BSGS(a,b,n); if(ans == -1)printf("no solution "); else printf("%d ",ans); } return 0; } 当p不为素数时,扩展bsgs. 当然也可以解决p为素数的 #include #include #include #include using namespace std; typedef long long LL; const int maxn = 65535; struct hash{ int a,b,next; }Hash[maxn << 1]; int flg[maxn + 66]; int top,idx; //hash值插入 void ins(int a,int b){ int k = b & maxn; if(flg[k] != idx){ flg[k] = idx; Hash[k].next = -1; Hash[k].a = a; Hash[k].b = b; return ; } while(Hash[k].next != -1){ if(Hash[k].b == b) return ; k = Hash[k].next; } Hash[k].next = ++ top; Hash[top].next = -1; Hash[top].a = a; Hash[top].b = b; } //hash值查找 int find(int b){ int k = b & maxn; if(flg[k] != idx) return -1; while(k != -1){ if(Hash[k].b == b) return Hash[k].a; k = Hash[k].next; } return -1; } int gcd(int a,int b) { return b?gcd(b,a%b):a; } //扩展欧几里得 int ext_gcd(int a,int b,int& x,int& y) { int t,ret; if (!b){x=1,y=0;return a;} ret=ext_gcd(b,a%b,x,y); t=x,x=y,y=t-a/b*y; return ret; } // 求逆元 int Inval(int a,int b,int n){ int x,y,e; ext_gcd(a,n,x,y); e=(LL)x*b%n; return e<0?e+n:e; } int pow_mod(LL a,int b,int c) { LL ret=1%c; a%=c; while(b){ if(b&1)ret=ret*a%c; a=a*a%c; b>>=1; } return ret; } //求解a^x = b (mod n) a, n互质 int BabyStep(int A,int B,int C){ top = maxn; ++ idx; LL buf=1%C,D=buf,K; int i,d=0,tmp; for(i=0;i<=100;buf=buf*A%C,++i) if(buf==B)return i; while((tmp=gcd(A,C))!=1){ if(B%tmp)return -1; ++d; C/=tmp; B/=tmp; D=D*A/tmp%C; } int M=(int)ceil(sqrt(C+0.5)); for(buf=1%C,i=0;i<=M;buf=buf*A%C,++i) ins(i,buf); for(i=0,K=pow_mod((LL)A,M,C);i<=M;D=D*K%C,++i){ tmp=Inval((int)D,B,C); int w ; if(tmp>=0&&(w = find(tmp)) != -1) return i*M+w+d; } return -1; } int main(){ int A,B,C; // K ^ D == N (mod P) while(scanf("%d%d%d",&A,&C,&B)!=EOF){// K P N if(B>C){ puts("Orz,I can’t find D!"); continue; } int tmp=BabyStep(A,B,C); if(tmp<0) puts("Orz,I can’t find D!"); else printf("%d ",tmp); } return 0; } 2.原根

给定一个数n,若存在一个与n互素的a,满足 ai(0<i<=φ(n)
在%n意义下的结果两两不同,则称a为n的一个原根.

原根的性质:
1.一般原根都比较小。
2.一个数n如果有原根，那么有  φ(φ(n))个
3.一个数n的全体原根乘积模n余1
4.一个数n的全体原根总和模n余μ(n-1)(莫比乌斯函数)
5.p为素数，当然φ(p)=p-1,因此就有φ(p-1)个原根
6. 所有的奇素数都有原根,原根素数为 φ(p-1)
哪些数有原根:
n=1,2,4,p^r,2p^r 其中p是奇素数,r是任意正整数
这里写图片描述 // 一般原根都很小 /* 求出n中所有的原根,若没有则直接输出-1*/ const int N = 1000000; bool f[N]; //计算欧拉筛复杂度为 根号n int phi(int x){ if(f[x]) return x-1; int ans = x; for(int i=2; i<=x; i++){ if(x%i==0){ while(x%i==0) x/=i; ans = ans - ans/i; } } if(x>1) ans = ans - ans/x; return ans; } int gcd(int a, int b){ swap(a,b); int c = a%b; while(c){ a=b; b=c; c=a%b; } return b; } int quick_mod(int x, int p, int mod){ long long s = 1; long long a = x; while(p){ if(p&1) s = (s*a)%mod; a = a*a%mod; p>>=1; } return (int)s; } vector<int> V; vector<int> G; void cal(int x){ G.clear(); if(f[x]) return; else{ for(int i=2; i*i<=x; i++){ if(x%i==0){ G.push_back(i); if(i*i!=x) G.push_back(x/i); } } } } //单次检验的复杂度为 log^2 n bool exist(int n){ if(n%2==0) n/=2; if(f[n]) return 1; for(int i=3; i*i<=n; i+=2){ if(n%i==0){ while(n%i==0) n/=i; return n==1; } } return 0; } void solve(int n){ if(n==2){ puts("1"); return; } if(n==4){ puts("3"); return; } if(!exist(n)){ puts("-1"); return; } int p = phi(n); cal(p); int x = -1; for(int i=2; ibool flag = 1; if(quick_mod(i, p, n)!=1) continue; for(int j=0; jif(quick_mod(i, G[j], n)==1){ flag = 0; break; } } if(flag){ V.resize(1); V[0] = x = i; break; } } if(x==-1){ puts("-1"); return; } for(int i=2; iif(gcd(i, p)==1) V.push_back(quick_mod(x, i, n)); } sort(V.begin(), V.end()); vector<int>::iterator it=unique(V.begin(), V.end()); V.erase(it, V.end()); for(int i=0; iif(i) putchar(' '); printf("%d", V[i]); } puts(""); } int main(){ memset(f, 1, sizeof(f)); f[0] = f[1] = 0; for(int i=2; iif(f[i]){ for(int j=i<<1; j0; } } int n; while(~scanf("%d", &n)) solve(n); return 0; }

热门文章