【LightOJ1370】Bi-shoe and Phi-shoe（欧拉函数）

题面

Vjudge

给出一些数字，对于每个数字找到一个欧拉函数值大于等于这个数的数，求找到的所有数的最小和。

题解

首先线性筛出欧拉函数值

排序之后倒着取min

最后\(O(n)\)求和即可

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define MAX 1200000

inline int read()

{

	int x=0,t=1;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=-1,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return x*t;

}

int phi[MAX+1000],zs[MAX+1000],pr[MAX],tot;

bool vis[MAX+1000];

int id[MAX+1000];

void Pre()

{

	vis[1]=true;

	for(int i=2;i<=MAX;++i)

	{

		if(!vis[i])pr[++tot]=i,phi[i]=i-1;

		for(int j=1;j<=tot&&i*pr[j]<=MAX;++j)

		{

			vis[i*pr[j]]=true;

			if(i%pr[j]==0){phi[i*pr[j]]=phi[i]*pr[j];break;}

			else phi[i*pr[j]]=phi[i]*(pr[j]-1);

		}

	}

}

bool cmp(int a,int b){if(phi[a]!=phi[b])return phi[a]<phi[b];return a<b;}

int mp[MAX+1000];

int main()

{

	Pre();

	for(int i=1;i<=MAX;++i)id[i]=i;

	memset(mp,63,sizeof(mp));

	for(int i=1;i<=MAX;++i)mp[phi[i]]=min(mp[phi[i]],i);

	for(int i=MAX-1;i;--i)mp[i]=min(mp[i+1],mp[i]);

	int T=read();

	for(int gg=1;gg<=T;++gg)

	{

		int n=read();

		long long ans=0;

		for(int i=1;i<=n;++i)ans+=mp[read()];

		printf("Case %d: %lld Xukha\n",gg,ans);

	}

	return 0;

}