求 x y ? m o d ? p x^y \bmod p xymodp。
long long power(long long x,int y){
long long res=1;
for(;y;y>>=1){
if(y&1)res=res*x%p;
x=x*x%p;
}
return res;
}
求 C n m ? m o d ? p C_n^m \bmod p Cnm?modp
long long fac[p],inv[P];
// 此处省略快速幂 power 函数
void init(){
fac[0]=inv[0]=1;
for(int i=1;i<P;++i)fac[i]=fac[i-1]*i%p,inv[i]=power(fac[i],p-2);
}
long long C(int n,int m,int p){
if(m>n)return 0;
return fac[n]*inv[n-m]%p*inv[m]%p;
}
long long Lucas(int n,int m,int p){
if(m==0)return 1;
return C(n%p,m%p,p)*Lucas(n/p,m/p,p)%p;
}
bool st[N];
int primes[N],tot=0;
void Eratosthenes(int n){
for(int i=2;i<=n;++i){
if(st[i])continue;
primes[++tot]=i;
for(int j=i;j<=n/i;++j)st[i*j]=true;
}
}
int st[N],primes[N],tot=0;
void Euler(int n){
for(int i=2;i<=n;++i){
if(!st[i])primes[++tot]=st[i]=i;
for(int j=1;j<=tot;++j){
if(primes[j]>st[i]||primes[j]>n/i)break;
st[i*primes[j]]=primes[j];
}
}
}
分解 n n n 的质因数,从小到大依次输出。
for(int i=2;i<=n/i;++i)
while(n%i==0)cout<<i<<' ',n/=i;
if(n!=1)cout<<n<<' ';
从小到大输出 n n n 的所有约数。
vector<int>s,t;
for(int i=1;i<=n/i;++i)
if(n%i==0){
s.push_back(i);
if(i!=n/i)t.push_back(n/i);
}
for(int i=0;i<s.size();++i)cout<<s[i]<<' ';
for(int i=t.size()-1;i>=0;--i)cout<<t[i]<<' ';
求 x x x 和 y y y 的最大公约数。
int gcd(int x,int y){
return y?gcd(y,x%y):x;
}
求 x x x 和 y y y 的最小公倍数。
//此处省略最大公约数 gcd 函数
long long lcm(int x,int y){
return(long long)x*y/gcd(x,y);
}
求 φ ( n ) \varphi(n) φ(n)。
int phi(int n){
int ans=n;
for(int i=2;i<=n/i;++i){
int c=0;
while(n%i==0)n/=i,c++;
if(c)ans=ans/i*(i-1);
}
if(n!=1)ans=ans/n*(n-1);
return ans;
}
int st[N],primes[N],phi[N],tot=0;
void getPhi(int n){
for(int i=2;i<=n;++i){
if(!st[i])primes[++tot]=st[i]=i,phi[i]=i-1;
for(int j=1;j<=tot;++j){
if(primes[j]>st[i]||primes[j]>n/i)break;
st[i*primes[j]]=primes[j];
if(i%primes[j]==0)phi[i*primes[j]]=phi[i]*primes[j];
else phi[i*primes[j]]=phi[i]*(primes[j]-1);
}
}
}
int st[N],primes[N],mu[N],tot=0;
void getPhi(int n){
for(int i=2;i<=n;++i){
if(!st[i])primes[++tot]=st[i]=i,mu[i]=-1;
for(int j=1;j<=tot;++j){
if(primes[j]>st[i]||primes[j]>n/i)break;
st[i*primes[j]]=primes[j];
if(i%primes[j]==0)mu[i*primes[j]]=0;
else mu[i*primes[j]]=-mu[i];
}
}
}