<题目链接>
<转载于 >>> >
题目大意：
给你n个整数，第i个整数为Xi。定义phi(k)为k的欧拉函数值，设pi为满足phi(pi)>=Xi的最小整数，题目就是要求sum(p1,p2,p3,...,pn)。
解题分析：
这题的思路很简单，只需打一张欧拉函数表，然后将Xi排序，再一一枚举即可，但是用常规方法做，用时会很长，下面介绍一种叫做欧拉筛的东西，类似于素数筛。
//欧拉筛法,快速筛出1-100万的欧拉函数值 const int maxn = 1000000; int phi[maxn+1]; bool isPrime[maxn+1]; 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; } } } }
接下来就是本题的代码
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int maxn = 1100000; int phi[maxn + 100]; bool isPrime[maxn + 100]; int arr[maxn + 100]; //欧拉筛法,快速筛出1-100万的欧拉函数值 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; } } } } int main() { int T, cas = 1; scanf("%d", &T); Eular(); while (T--) { int n, x; scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &arr[i]); } sort(arr + 1, arr + n + 1); long long sum = 0; for (int i = 1, j = 2; i <= n && j <= maxn; j++) { if (phi[j] >= arr[i]) { sum += j; i++; j--; //注意这里一定要记得j--,因为后面的arr[i+1]对应的答案可能也是phi[i] } } printf("Case %d: %lld Xukha\n", cas++, sum); } return 0; }
2018-07-31
原文：https://www.cnblogs.com/00isok/p/9399020.html