模板 数论

GCD

#include<cstdio>
#include<iostream>
using namespace std;
long long gcd(int x,int y){
    if(x%y==0) return y;
    else return gcd(y,x%y);
}
int main(){
    long long M,N;
    cin>>M>>N;
    cout<<gcd(M,N)<<endl;
    return 0;
}

bigint gcd(bigint x,bigint){
    // Make sure x>y
    if(x<=y) swap(x,y);
    if(y==0) return x;
    if((x%2==0)&&(y%2==0)) return gcd(x>>1,y>>1)<<1;
    if(x%2==0) return gcd(x>>1,y);
    if(y%2==0) return gcd(x,y>>1);
    return gcd(y,x-y);//Attention!
}

int exGcd(int a,int b,int &x,int &y)  
{  
    if(b==0)  
    {  
        x=1;y=0;  
        return a;
        // 此时a = gcd(A,B)  
        // a * 1 + b * 0 = gcd(A,B)
        // 由于b=0，y可以任意取值
    }  
    int d=exGcd(b,a%b,y,x); // 注意这里x，y的位置对调  
        y-=a/b*x;  
        return d; // 返回最大公约数  
    }  
    
    
/*原Gcd*/
int gcd(int a,int b)
{
    if(b==0) return a;
    else     return gcd(b,a%b);
} 

LCM

#include <iostream>
using namespace std;
/* 欧几里得算法：递归法计算最大公约数 */
long long gcd(long long m, long long n)
{
    return (m==0)?n:gcd(n%m, m);
}

// 计算最小公倍数函数
long long lcm(long long a, long long b)
{
   return a/gcd(a,b)*b;
}

int main()
{
    int a,b;
    cin>>a>>b;
    cout<<lcm(a,b)<<endl;
    return 0;
}

CRT

#include<cstdio>
#include<iostream>
using namespace std;
int exgcd(int a,int b,int &x,int &y){
    if(b==0){
        x=1,y=0;
        return a;
    }
    int gcd=exgcd(b,a%b,x,y);
    int t=x;
    x=y;
    y=t-a/b*y;
    return gcd;
} 
int CRT(int W[],int B[],int k){//W为按多少排列，B为剩余个数，W>B，k为组数 
    int x,y,a=0,m,n=1;
    for(int i=0;i<k;i++) n*=W[i];
    for(int i=0;i<k;i++) {
        m=n/W[i];
        exgcd(W[i],m,x,y);
        a=(a+y*m*B[i])%n;
    }
    if(a>0) return a;
    else return a+n;
}




/*以下是longlong版本*/
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL; 
LL exgcd(LL a,LL b,LL &x,LL &y){
    if(b==0){
        x=1,y=0;
        return a;
    }
    int gcd=exgcd(b,a%b,x,y);
    int t=x;
    x=y;
    y=t-a/b*y;
    return gcd;
} 
LL CRT(LL W[],LL B[],LL k){
    LL x,y,a=0,m,n=1;
    for(int i=0;i<k;i++) n*=W[i];
    for(int i=0;i<k;i++) {
        m=n/W[i];
        exgcd(W[i],m,x,y);
        a=(a+y*m*B[i])%n;
    }
    if(a>0) return a;
    else return a+n;
} 

euler

//直接求解欧拉函数
int euler(int n){ //返回euler(n) 
     int res=n,a=n;
     for(int i=2;i*i<=a;i++){
         if(a%i==0){
             res=res/i*(i-1);//先进行除法是为了防止中间数据的溢出 
             while(a%i==0) a/=i;
         }
     }
     if(a>1) res=res/a*(a-1);
     return res;
}

//筛选法打欧拉函数表 
#define Max 1000001
int euler[Max];
void Init(){ 
     euler[1]=1;
     for(int i=2;i<Max;i++)
       euler[i]=i;
     for(int i=2;i<Max;i++)
        if(euler[i]==i)
           for(int j=i;j<Max;j+=i)
              euler[j]=euler[j]/i*(i-1);//先进行除法是为了防止中间数据的溢出 
}

素数筛

void shaifa(){
    for(int i=2;i<=n;i++) 
        for(int j=2*i;j<=n;j+=i)
            not_prime[j]=true;
} 
//nlogn by zhx

void shaifa(){
    for(int i=2;i<=n;i++) 
        if(!not_prime[i])
            for(int j=2*i;j<=n;j+=i)
                not_prime[j]=true;
} 
//nloglogn by zhx

#include <cstring>
using namespace std;
int prime[1100000],primesize,phi[11000000];
bool isprime[11000000];
void getlist(int listsize)
{
    memset(isprime,1,sizeof(isprime));
    isprime[1]=false;
    for(int i=2;i<=listsize;i++)
    {
        if(isprime[i])prime[++primesize]=i;
         for(int j=1;j<=primesize&&i*prime[j]<=listsize;j++)
         {
            isprime[i*prime[j]]=false;
            if(i%prime[j]==0)break;
        }
    }
}