打算存点数论板子
1.GCD与LCM
gcd(a,b)=gcd(b,a%b);
更相减损术：
gcd(a,b)=gcd(a,b-a);
记录一下昨晚的题：传送门添加链接描述
2.质因数分解（唯一分解定理）
void divide(int x){ for(int i=2;i<=x/i;i++) if(x%i==0){ int s=0; while(x%i==0) x/=i,s++; cout<<i<<" "<<s<<endl; } if(x>1) cout<<x<<" "<<1<<endl; cout<<endl; }
3.质数筛
int pri[N],cnt; bool st[N]; void prim(int x){ for(int i=2;i<=x;i++){ if(!st[i]){ pri[cnt++]=i; for(int j=i+i;j<=x;j+=i) st[j]=true; } } }
欧拉筛
int pri[N],cnt; bool st[N]; void prim(int x){ for(int i=2;i<=x;i++){ if(!st[i]) pri[cnt++]=i; for(int j=0;pri[j]<=x/i;j++){ st[pri[j]*i]=true; if(i%pri[j]==0) break; } } }
4.试除法求约数
vector<int> get_divisors(int x) { vector<int> res; for (int i = 1; i <= x / i; i ++ ) if (x % i == 0) { res.push_back(i); if (i != x / i) res.push_back(x / i); } sort(res.begin(), res.end()); return res; }
5.约数个数
如果 N = p1^c1 * p2^c2 * … *pk^ck
约数个数： (c1 + 1) * (c2 + 1) * … * (ck + 1)
约数之和： (p1^0 + p1^1 + … + p1^c1) * … * (pk^0 + pk^1 + … + pk^ck)
unordered_map<int, int> primes; while (n -- ) { int x; cin >> x; for (int i = 2; i <= x / i; i ++ ) while (x % i == 0) { x /= i; primes[i] ++ ; } if (x > 1) primes[x] ++ ; } LL res = 1; for (auto p : primes) res = res * (p.second + 1) % mod;
6.约数之和
unordered_map<int, int> primes; while (n -- ) { int x; cin >> x; for (int i = 2; i <= x / i; i ++ ) while (x % i == 0) { x /= i; primes[i] ++ ; } if (x > 1) primes[x] ++ ; } LL res = 1; for (auto p : primes) { LL a = p.first, b = p.second; LL t = 1; while (b -- ) t = (t * a + 1) % mod; res = res * t % mod; }
7.欧拉函数
1 ~ N 中与 N 互质的数的个数被称为欧拉函数
int a; cin>>a; int res=a; for(int i=2;i<=a/i;i++) if(a%i==0){ res=res/i*(i-1); while(a%i==0) a/=i; } if(a>1) res=res/a*(a-1); cout<<res<<endl;
8.筛法求欧拉函数
int prime[N],cnt,phi[N]; bool st[N]; ll get_eulers(int n){ phi[1]=1; for(int i=2;i<=n;i++){ if(!st[i]){ prime[cnt++]=i; phi[i]=i-1; } for(int j=0;prime[j]<=n/i;j++){ st[prime[j]*i]=true; if(i%prime[j]==0){ phi[i*prime[j]]=prime[j]*phi[i]; break; } phi[i*prime[j]]=(prime[j]-1)*phi[i]; } } ll res=0; for(int i=1;i<=n;i++) res+=phi[i]; return res; }
9.快速幂
ll ksm(ll a,ll b,ll p){ ll res=1; a%=p; while(b){ //&运算当相应位上的数都是1时，该位取1，否则该为0。 if(b&1) res=1ll*res*a%p;//转换为ll型 a=1ll*a*a%p; b>>=1;//十进制下每除10整数位就退一位 } return res; }
10.龟速乘
求 a 乘 b 对 p 取模的值。
1≤a,b,p≤10^18
ll cul(ll a,ll b,ll p){ ll res=0; while(b){ if(b&1) res=(res+a)%p; a=(a+a)%p; b>>=1; } return res; }
11.乘法逆元
若整数b，m互质，并且对于任意的整数 a，如果满足b|a，则存在一个整数x，使得a/b≡a∗x(mod m)，则称x为b的模m乘法逆元，记为b−1(mod m)。
b存在乘法逆元的充要条件是b与模数m互质。当模数m为质数时，bm−2即为b的乘法逆元。
cin>>a>>p; if(a%p==0) puts("impossible"); else cout<<ksm(a,p-2,p)<<endl;
12.扩展欧几里得算法
给定n对正整数ai,bi，对于每对数，求出一组xi,yi，使其满足ai∗xi+bi∗yi=gcd(ai,bi)。
int exgcd(int a,int b,int &x,int &y){ if(!b){ x=1,y=0; return a; } int d=exgcd(b,a%b,y,x); y-=a/b*x; return d; }
13.中国剩余定理
给定 2n 个整数a1,a2,…,an和m1,m2,…,mn,求一个最小的非负整数 x，满足 ∀i∈[1,n],x≡mi(mod ai) 。
14.高斯消元
15.矩阵乘法
来自AcWing
