【kuangbin带你飞 数论基础】欧拉函数模板（总结）

A - Bi-shoe and Phi-shoe
欧拉函数讲解博客
欧拉函数快速筛法

欧拉函数：欧拉函数phi(x)代表小于等于x的数中和x互质（没有除1以外的公因子）的数的个数，比如说小于等于9的数中与9互质的有1，2，4，5，7，8，则phi(9)=6.

欧拉指出，以phi(x)表示小于等于x的数中与x互质的数的个数可以这样得到：

phi(x) = x*(1-1/p1)*(1-1/p2)*(1-1/p3)...*(1-1/pn)

其中p1,p2,p3…pn是x的所有质因数，每个质因数只使用一次，使用上述公式，则phi(9)=9*(1-1/3)=6.

效仿素数筛法的欧拉筛。
欧拉函数也有其快速筛算法。

欧拉筛法的原理如下，我们观察phi(x)的求解式子，首先令phi(x)=x,然后仿照素数筛法，如果x能被2,3,5,7…筛到，则执行phi(x)=phi(x)*(1-1/prime)

void Eular()
{
   
    for(int i=1;i<=maxn;i++) phi[i]=i;
    memset(isPrime,true,sizeof(isPrime));
    isPrime[0]=isPrime[1]=false;
    phi[1]=0;
    for(int i=2;i<=maxn;i++)
    {
   
        if(isPrime[i])
        {
   
            for(int j=i;j<=maxn;j+=i)
            {
   
                isPrime[j]=false;
                phi[j] -= phi[j]/i;
            }
        }
    }
}

A题代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+1000;
int isp[maxn];
int phi[maxn];
void get_phi()
{
   
	int i,j;
	for(i=0; i<=maxn; i++) {
   
		isp[i]=1; phi[i]=i;
	}
	isp[0]=isp[1]=0;
	phi[1]=0;
	for(i=2; i*i<=maxn; i++) {
   
		if(isp[i]==1) {
   
			for(j=i; j<=maxn; j+=i) {
   
				isp[j]=0;
				phi[j] -= phi[j]/i;
			}
		}
	}
}

int main()
{
   
	int t;
	scanf("%d", &t);
	get_phi();
	for(int k=1; k<=t; k++) {
   
		long long sum=0;
		int n;
		scanf("%d", &n);
		for(int i=1; i<=n; i++) {
   
			int x;
			scanf("%d", &x);
			for(int j=x+1; j<=maxn; j++) {
   
				if(phi[j]>=x) {
   
					sum+=j;
					break; 
				}
			}
		}
		printf("Case %d: %lld Xukha\n",k,sum);
	}
	return 0;
}