一：
1.欧几里得求最大公约数

int _gcd(int x,int y)
{
    return y?_gcd(y,x%y):x;
}

2.最小公倍数

#include <bits/stdc++.h>
using namespace std;
int gcd(int x,int y)
{
    return y?gcd(y,x%y):x;
}
int main()
{
    int n,a;
    while(scanf("%d",&n)!=EOF)
    {
        int ans=1;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a);
            ans=ans/gcd(ans,a)*a;//注意先除后乘
        }
        printf("%d\n",ans);
    }
    return 0;
}

3.素因子分解( 复杂度:sqrt(n) )
当n比较大时，可以先用欧拉筛筛出sqrt(n)范围内的素数，然后把for循环里面的i换成对素数的遍历。

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int factor[N],e[N];//factor[]:用来存素因子个数，(可以用vector代替)e[]:用来存对应的素因子的幂
int divide(int num)
{
    int tn=num,cnt=0;
    memset(e,0,sizeof(e));
    for(int i=2;i*i<=num;i++)//sqrt(n)的复杂度
    {
        if(tn%i==0)
        {
            factor[++cnt]=i;
            while(tn%i==0)
            {
                e[cnt]++;
                tn/=i;
            }
        }
    }
    if(tn>1)//不能省略！
    {
        factor[++cnt]=tn;
        e[cnt]++;
    }
    return cnt;
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        int cot=divide(n);
        printf("%d:",n);
        for(int i=1;i<=cot;i++)//输出各个素因子
        {
            while(e[i]--)//幂
                printf(" %d",factor[i]);
        }
        puts("");
    }
    return 0;
}

4.快速幂取模
函数里面的数据类型都用long long 容易爆int

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
ll POW(ll x,ll y)
{
    ll res=1;
    while(y)
    {
        if(y&1)
            res=res*x%mod;//易爆int
        x=x*x%mod;//易爆int
        y>>=1;
    }
    return res%mod;
}
int main()
{
    int n,m;
    while(scanf("%d%d",&m,&n)!=EOF)
    {
        printf("%lld\n",POW((ll)m,(ll)n));//int会超数据范围
    }
    return 0;
}

5.求一个数的欧拉函数值
数据复杂度：sqrt(n)

#include <bits/stdc++.h>
using namespace std;
int phi(int num)
{
    int res=num;
    for(int i=2;i*i<=num;i++)
    {
        if(num%i==0)
        {
            res-=(res/i);
            while(num%i==0)
                num/=i;
        }
    }
    if(num>1)
        res-=(res/num);
    return res;
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        printf("%d\n",phi(n));
    }
    return 0;
}

6.欧拉筛筛 N 以内的素数
时间复杂度：O(n)

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
bool vis[N];//标记非素数
vector<int>prime;//保存素数
void euler()
{
    prime.clear();
    memset(vis,0,sizeof(vis));
    for(int i=2;i<N;i++)
    {
        if(!vis[i])
            prime.push_back(i);
        for(int j=0;j<prime.size()&&i*prime[j]<N;j++)
        {
            vis[i*prime[j]]=1;
            if(i%prime[j]==0)
                break;
        }
    }
}
int main()
{
    euler();
    
    return 0;
}

7.欧拉筛筛 N 以内的所有数的欧拉函数值
时间复杂度：O(n)

const int N=1e5+5;
int phi[N];//存欧拉函数值
bool vis[N];//标记非素数
vector<int>prime;//存素数
void euler()
{
    memset(vis,0,sizeof(vis));
    //memset(phi,0,sizeof(phi));
    prime.clear();
    phi[1]=1;//预处理phi[1]
    for(int i=2;i<N;i++)
    {
        if(!vis[i])
        {
            prime.push_back(i);
            phi[i]=i-1;//素数的欧拉函数值的性质
        }
        for(int j=0;j<prime.size()&&i*prime[j]<N;j++)
        {
            vis[i*prime[j]]=1;
            if(i%prime[j]==0)
            {
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            else
                phi[i*prime[j]]=phi[i]*phi[prime[j]];//积性函数的性质
        }
    }
}

8.欧拉筛筛莫比乌斯函数值
时间复杂度：O(n)

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
vector<int>prime;
int mob[N];
bool vis[N];
void mobius()
{
    prime.clear();
    memset(vis,0,sizeof(vis));
    mob[1]=1;//莫比乌斯函数第一类情况
    for(int i=2;i<N;i++)
    {
        if(!vis[i])
        {
            prime.push_back(i);
            mob[i]=-1;//素数
        }
        for(int j=0;j<prime.size()&&prime[j]*i<N;j++)
        {
            int tmp=i*prime[j];
            vis[tmp]=1;
            if(i%prime[j]==0)
            {
                mob[tmp]=0;//其他情况，因为prime[j]是i的因子，所以k的因子中含有的prime[j]的个数不是1
                break;
            }
            else
               mob[tmp]=-mob[i];//积性函数的性质
        }
    }
}
int main()
{
    mobius();
    for(int i=1;i<=10;i++)
        cout<<mob[i]<<endl;
    return 0;
}

二：