1.欧几里得
#include<cstdio>
using namespace std;
int a,b;
int gcd(int x,int y){
if(y==0)return x;
return gcd(y,x%y);
}
int main(){
scanf("%d%d",&a,&b);
printf("%d",gcd(a,b));
}
2.扩展欧几里得
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
#define ll long long
ll a,b,x,y;
ll exgcd(ll a,ll b){
if(b==0){
x=1;y=0;
return a;
}
exgcd(b,a%b);
ll tmp=x;
x=y;y=tmp-(a/b)*y;
}
int main(){
scanf("%lld%lld",&a,&b);
exgcd(a,b);
while(x<0)x+=b;
cout<<x;
}
3.欧拉筛
void prepare(){
for(int i=2;i<=n;i++){
if(!vis[i])p[++cnt]=i;
for(int j=1;j<=cnt&&i*p[j]<=n;j++){
vis[i*p[j]]=1;
if(i%p[j]==0)break;
}
}
}
4.欧拉函数
int euler_phi(int n){//单个欧拉函数
int m=(int)sqrt(n+0.5);
int ans=n;
for(int i=2;i<=m;i++)if(n%i==0){
ans=ans/i*(i-1);
while(n%i==0)n/=i;
}
if(n>1)ans=ans/n*(n-1);
}
void prepare(){//函数表
phi[1]=1;
for(int i=2;i<=1000;i++){
if(!vis[i])p[++p[0]]=i,phi[i]=i-1;
for(int j=1;j<=p[0]&&i*p[j]<=1000;j++){
vis[i*p[j]]=1;
if(i%p[j]==0){
phi[i*p[j]]=phi[i]*p[j];
break;
}
else phi[i*p[j]]=phi[i]*(p[j]-1);
}
}
}
5.中国剩余定理
/*
x=p(mod 23)
x=e(mod 28)
x=i(mod 33)
题目就是要求上面同余方程的解,用中国剩余定理求解
*/
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int a[5],m[5];
void Exgcd(int a,int b,int &x,int &y){
if(b==0){x=1;y=0;return;}
Exgcd(b,a%b,x,y);
int tmp=x;
x=y;
y=tmp-(a/b)*y;
}
int CRT(int a[],int m[],int n){
int M=1,ans=0;
for(int i=1;i<=n;i++)M*=m[i];
for(int i=1;i<=n;i++){
int x,y,Mi=M/m[i];
Exgcd(Mi,m[i],x,y);
ans=(ans+Mi*x*a[i])%M;
}
if(ans<0)ans+=M;
return ans;
}
int main(){
freopen("Cola.txt","r",stdin);
int p,e,i,d,Case=0;
while(1){
Case++;
scanf("%d%d%d%d",&p,&e,&i,&d);
if(p==-1&&e==-1&&i==-1&&d==-1)return 0;
a[1]=p;a[2]=e;a[3]=i;
m[1]=23;m[2]=28;m[3]=33;
int ans=CRT(a,m,3);
if(ans<=d)ans+=21252;
printf("Case %d: the next triple peak occurs in %d days.
",Case,ans-d);
}
}
6.卡特兰数
#include<iostream> //没有取模操作
#include<cstdio>
using namespace std;
long long h[20];
int main(){
int n;
scanf("%d",&n);
h[0]=1;h[1]=1;
for(int i=2;i<=n;i++)h[i]=h[i-1]*(4*i-2)/(i+1);
cout<<h[n];
}
/*注意不要用另类递推式,因为里面的除法在取模的时候会出问题*/
#include<cstdio>//有取模操作
using namespace std;
int h[110];
int main(){
int n,i,j;
h[0]=1;
scanf("%d",&n);
for(i=1;i<=n;++i)
for(j=0;j<i;++j)
h[i]=(h[i]+h[j]*h[i-1-j])%100;
printf("%d
",h[n]);
return 0;
}
7.逆元(求组合数)
#include<iostream>//O(n)预处理+O(1)查询
#include<cstdio>
#define N 200001
#define mod 1000000007
using namespace std;
long long fac[N]={1,1},inv[N]={1,1},f[N]={1,1};
int n,m;
long long C(int x,int y){
return fac[x]*inv[y]%mod*inv[x-y]%mod;
}
int main(){
for(int i=2;i<N;i++){
fac[i]=fac[i-1]*i%mod;
f[i]=(mod-mod/i)*f[mod%i]%mod;
inv[i]=inv[i-1]*f[i]%mod;
}
while(scanf("%d%d",&n,&m)!=EOF){
cout<<C(n+m-4,m-2)<<endl;
}
return 0;
}
#include<iostream>//费马小定理
#include<cstdio>
#define mod 1000000007
using namespace std;
long long fac[1000001];
int n,m;
long long Pow(long long a,long long b){
long long res=1;
while(b){
if(b&1)res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
long long C(int x,int y){
return fac[x]*Pow(fac[y],mod-2)%mod*Pow(fac[x-y],mod-2)%mod;
}
int main(){
fac[1]=1;fac[0]=1;
for(int i=2;i<=1000000;i++)fac[i]=fac[i-1]*i%mod;
while(scanf("%d%d",&n,&m)!=EOF){
cout<<C(n+m-4,m-2)<<endl;
}
}
8.卢卡斯定理(求组合数取模)
#include<bits/stdc++.h>
#define N 100010
using namespace std;
typedef long long ll;
ll a[N];
int p;
ll pow(ll y,int z,int p){
ll res=1;y%=p;
while(z){
if(z&1)res=res*y%p;
y=y*y%p;
z>>=1;
}
return res;
}
ll C(ll n,ll m){
if(m>n)return 0;
return ((a[n]*pow(a[m],p-2,p))%p*pow(a[n-m],p-2,p)%p);
}
ll Lucas(ll n,ll m){
if(!m)return 1;
return C(n%p,m%p)*Lucas(n/p,m/p)%p;
}
int main(){
int T;scanf("%d",&T);
int n,m;
while(T--){
scanf("%d%d%d",&n,&m,&p);
a[0]=1;
for(int i=1;i<=p;i++)a[i]=(a[i-1]*i)%p;
cout<<Lucas(n+m,n)<<endl;
}
}