线性筛素数
#include<cstdio>
#include<cmath>
#include<cstring>
const int maxn=10000005;
int n,m;
bool isp[maxn];
int p[int(2*maxn/log(maxn))],cnt;
int main()
{
scanf("%d%d",&n,&m);
memset(isp,true,sizeof(isp));
isp[1]=false;
for(int i=2;i<=n;i++)
{
if(isp[i]) p[cnt++]=i;
for(int j=0;j<cnt&&i*p[j]<=n;j++)
{
isp[i*p[j]]=false;
if(i%p[j]==0) break;
}
}
while(m-->0)
{
scanf("%d",&n);
puts(isp[n]?"Yes":"No");
}
return 0;
}
指数判定与质因数分解（Pollard-Rho与Miller Rabin）
代码：
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int ps[]={2,3,5,7,11,13,17,19,23,29,31,37};
const int pcnt=sizeof(ps)/sizeof(int);
inline LL mt(LL a,LL b,LL m)
{
LL d=((long double)a/m*b+1e-8);
LL r=a*b-d*m;
return r<0?r+m:r;
}
inline LL mpow(LL a,LL b,LL m)
{
LL res=1;
for(;b;b>>=1,a=mt(a,a,m)) if(b&1) res=mt(res,a,m);
return res;
}
inline LL gcd(LL a,LL b)
{
if(!a||!b) return a+b;
int t=__builtin_ctzll(a|b);
a>>=__builtin_ctzll(a);
do
{
b>>=__builtin_ctzll(b);
if(a>b) { LL t=b; b=a; a=t; }
b-=a;
}
while(b!=0);
return a<<t;
}
inline int isp(LL n)
{
if(n==1) return 0;
if(n==2||n==3||n==5) return 1;
if(!(n&1)||(n%3==0)||(n%5==0)) return 0;
LL m=n-1; int k=0;
while(!(m&1)) m>>=1,++k;
for(int i=0;i<pcnt&&ps[i]<n;++i)
{
LL x=mpow(ps[i],m,n),y=x;
for(int i=0;i<k;++i)
{
x=mt(x,x,n);
if(x==1&&y!=1&&y!=n-1) return 0;
y=x;
}
if(x!=1) return 0;
}
return 1;
}
LL f[105]; int cnt;
inline LL nxt(LL x,LL n,LL a)
{
LL t=mt(x,x,n)+a;
return t<n?t:t-n;
}
const int M=(1<<7)-1;
inline LL rho(LL n)
{
if(n%2==0) return 2; if(n%3==0) return 3;
LL x=0,y=0,t=1,q=1,a=(rand()%(n-1))+1;
for(int k=2;true;k<<=1,y=x,q=1)
{
for(int i=1;i<k;++i)
{
x=nxt(x,n,a);
q=mt(q,abs(x-y),n);
if(!(i&M))
{
t=gcd(q,n);
if(t>1) break;
}
}
if(t>1||(t=gcd(q,n))>1) break;
}
if(t==n) for(t=1;t==1;t=gcd(abs((x=nxt(x,n,a))-y),n));
return t;
}
void solve(LL n)
{
if(n==1) return;
if(isp(n)) { f[cnt++]=n; return; }
LL t=n; while(t==n) t=rho(n);
solve(t); solve(n/t);
}
int main()
{
int T; LL n;
scanf("%d",&T);
while(T-->0)
{
scanf("%lld",&n);
cnt=0; solve(n); sort(f,f+cnt);
if(cnt==1) puts("Prime");
else printf("%lld
",f[cnt-1]);
}
return 0;
}
严格O(log n)的质因数分解
#include<cstdio>
const int MN=300000;
const int MX=15000000;
int u[MX+5],p[MX+5],pn;
//u[i]=i的最小质因子
int main()
{
int n,i,j;
for(i=2;i<=MX;++i)
{
if(!u[i]) u[i]=p[++pn]=i;
for(j=1;i*p[j]<=MX;++j) { u[i*p[j]]=p[j]; if(i%p[j]==0) break; }
}
scanf("%d",&n);
for(;n>1;) printf("%d ",u[n]),n/=u[n];
return 0;
}
欧几里得算法与拓展欧几里得（拓欧）
#include<cstdio>
typedef long long LL;
LL a,b,x,y;
LL exgcd(LL a,LL b,LL &x,LL &y)
{
if(b==0) { x=1; y=0; return a; }
LL d=exgcd(b,a%b,y,x);
y-=x*(a/b);
return d;
}
int main()
{
#ifdef local
freopen("pro.in","r",stdin);
#endif
scanf("%lld%lld",&a,&b);
exgcd(a,b,x,y);
printf("%lld %lld
",x,y);
return 0;
}
得出的(x_0)和(y_0)满足(ax_0+by_0=gcd(a,b))，方程(ax+by=c)的通解可表示为：
$ x= frac{c}{d} x_0+k frac{b}{d}, y= frac{c}{d} y_0 - k frac{a}{d} (k in mathbb{Z}) $ （有解当且仅当$ d|c $）
费马小定理、欧拉定理与拓展欧拉定理
欧拉定理：若正整数(a)和(n)互质，则$ large a^{phi (n) } equiv 1 (mod ext{ }n)(
推论：若正整数)a(和)n(互质，则对于任何正整数)b(，有) large a^b equiv a^{b ext{ } mod ext{ } phi (n)} (mod ext{ } n)$
拓展欧拉定理：对于任何正整数 (a,b,n) ，且 $ b > phi (n) $ 时，有 $ large a^b equiv a^{b ext{ } mod ext{ } phi (n) + phi (n) } (mod ext{ } n)$ （ (a) 和 (n) 不一定互质）
拓展中国剩余定理
令前k-1个方程的解为x，记$$L=lcm(m_1,m_2,...,m_{k-1})$$，则 $ x + i * m $ 为前k-1个方程的通解。
在第k个方程中，令 $ x + t * L equiv a_k pmod{ m_k }$
即 $$ L * t equiv a_k - x pmod{ m_k } $$
令 $ d = exgcd( L , m_k , t , r ) $，则 $ t = ( a_k - x) / d * t $ ， $ x = x + t * L $
注意：记得取模
代码：
LL exgcd(LL a,LL b,LL &x,LL &y)
{
if(b==0) { x=1; y=0; return a; }
LL d=exgcd(b,a%b,y,x);
y-=x*(a/b);
return d;
}
int n;
LL x,L,t,r,a,m,d;
int main()
{
#ifdef local
freopen("pro.in","r",stdin);
#endif
scanf("%d",&n);
scanf("%lld%lld",&m,&a); x=a; L=m;
for(int i=2;i<=n;i++)
{
scanf("%lld%lld",&m,&a);
d=exgcd(L,m,t,r);
x+=((a-x)%m+m)%m/d*t*L;
L=L/d*m;
x=(x%L+L)%L;
}
printf("%lld
",x);
return 0;
}
线性基
线性基本质上是一个和原有数集的异或空间相同的数集（把每个数二进制化后看成向量），可以搭配异或相关的计算。
求线性基有2种方法：
1.高斯消元(O(n^2 log n))
2.贪心法(O(n log n))
代码（贪心法）：
//依次用输入数集调用cal函数，p数组即为线性基，p[i]表示最高为在第i位的数（向量）
void cal(LL x)
{
for(int i=62;i>=0;i--)
{
if(!(x>>i)) continue;
if(!p[i])//唯一且不可替代
{
p[i]=x;
break;
}
x^=p[i];//这一位没用了，作个基本行变换
}
}
逆元
费马小定理
inline int inv(int a,int b) { return ksm(a,b-2); }
欧拉定理
inline int inv(int a,int b) { return ksm(a,phi(b)-1); }
exgcd
inline int inv(int a,int b)
{
int x,y;
exgcd(a,b,x,y);
return x;
}
线性递推逆元
inv[1]=1;
for(int i=2;i<=n;i++) inv[i]=(p-p/i)*inv[p%i]%p;
线性递推阶乘逆元
inv[1]=1;
for(int i=2;i<=n;i++) inv[i]=(p-p/i)*inv[p%i]%p;
invf[0]=1;
for(int i=1;i<=n;i++) invf[i]=invf[i-1]*inv[i]%p;