容斥原理

求出一个数n在区间[1,m]里面有多少个数与它互质。假设数据不超过int型。

实现过程分为两步：

1.求出m的质因子 并保存在数组里面；

2.求出区间[1,n]里面有多少个数与m不互质。

二进制法：

出现奇数个数，就用加法，偶数个数用减法。
设质因数的个数为m。
有一个数字，它的二进制的每一位表示用了哪些数字，
比如5（101），其二进制的第一位和第三位（倒着数）是1，
则它表示用了第一个质因数和第三个质因数。
从1到m遍历一遍，就把所有的可能都包括了。

int pri[15];     //int型n不会超过10个
int num;
void pr(int n)     //求n的质因子 
{
    int i;
    num=0;
    for(i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            pri[num++]=i;
            while(n%i==0)
            n=n/i; 
        }
    }
    if(n>1)pri[num++]=n;
}
long long copr(long long x)
{
    int s,j;
    long long i;
    long long sum,res=0;
    for(i=1;i<(long long)1<<num;i++)     //1<<num相当于2的num次方 
    {
        s=0;     //1的个数
        sum=1;
        for(j=0;j<num;j++)
        {
            if(((long long)1<<j)&i)     //该结果不为0则倒数第j+1位为1
            {
                sum=sum*pri[j];
                s++;
            } 
        }
        if(s%2==1)res=res+x/sum;
        else res=res-x/sum;
    }
    return res;
}

队列法：

int pri[15];
int num;
long long zh[10100];     //保存组合的乘积及正负号 
void pr(int n)     //求n的质因子 
{
    int i;
    num=0;
    for(i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            pri[num++]=i;
            while(n%i==0)
            n=n/i; 
        }
    }
    if(n>1)pri[num++]=n;
}
long long copr(long long x)
{
    int top=0,t,i,j; 
    long long res=0;
    zh[top++]=-1;
    for(i=0;i<num;i++)
    {
        t=top;
        for(j=0;j<t;j++)
        zh[top++]=zh[j]pri[i](-1);
    }
    for(i=1;i<top;i++)
    res=res+x/zh[i];
    return res;
}

欧拉函数

指一个数n在[1,n-1]区间有多少个数与它互质。

比如说，φ[n] = m代表的意思是在区间[1,n-1]里面有m个数与n互质。

欧拉函数公式：（我们假设n的质因子有x,y（重复的只算一次）） $φ[n]=n*(1-\frac{1}{x}) * (1-\frac{1}{y})$。若有多个继续添上即可。

下面介绍一些基本性质：

1.n≥1,φ(1)=1。

2.当n为质数的时候，φ(n)=n−1。

3.欧拉函数是积性函数，但不是完全积性。当n,m互质的时候，φ(n∗m)=φ(n)∗φ(m)。

4.当n为奇数的时候，φ(2∗n)=φ(n)。

5.除了φ(2)时，其他欧拉函数均为偶数。

6.小于n，且与n互质的所有数字的和是$\frac{φ(n)∗n}{2}$。

求欧拉函数 有两个思路：

1.筛法，用数组记录每个数的欧拉函数（适用于n不是很大的情况，因为数组不能开无限大）；

2.直接求法计算单个欧拉函数，对于有些题目会比较慢（对于很大的n依然可以求解）；

3.线性筛。

int eu[10001];
void euler(int n)
{
    memset(eu,0,sizeof(eu));
    eu[1]=1;
    for(int i=2;i<10001;i++)
    if(eu[i]==0)
    {
        for(int j=i;j<10001;j=j+i)
        {
            if(eu[j]==0)eu[j]=j;
            eu[j]=eu[j]/i*(i-1);
        }
    }
}

int euler(int n)
{
    int i,res=n;
    int temp=res;   //如果要记忆化的话
    for(i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            res=res/i*(i-1);     //先除防溢出；不能只能乘(1-1/i)会变成0
            while(n%i==0)     //去重
            n=n/i;
        }
    }
    if(n>1)res=res/n*(n-1);     //本来就是质数
    //phi[temp]=res;   //如果要记忆化的话
    return res;
}

#define MAXN 20000001
ll eu[MAXN];
ll pri[MAXN];
bool vis[MAXN];
void init()
{
    eu[1]=1;
    ll cnt=0;
    for(ll i=2;i<MAXN;i++)
    {
        if(!vis[i]){pri[cnt++]=i;eu[i]=i-1;}
        for(int j=0;j<cnt&&pri[j]*i<MAXN;j++)
        {
            vis[i*pri[j]]=1;
            if(i%pri[j]==0)
            {
                eu[i*pri[j]]=eu[i]*pri[j];
                break;
            }
            eu[i*pri[j]]=eu[i]*(pri[j]-1);
        }
    }
}