AcWing 4575. Bi数和Phi数

题意:

就是给你n个数，对于每一个数y你都需要找到一个最小x使得$\varphi (x)\ge y$，然后再求一个最小平和。

思路:

其实最开始以来的思路就是二分，我先进行线性筛求出每个数的欧拉函数，然后二分去找到第一个大于等于a[i]的欧拉函数，看起来确实挺合理的，但是题目要求我们找到最小满足条件的x不是最小满足条件的phi(x)。举一个例子，对于1000来说如果按照我们上述的样例我们找到的x应该是1111，phi(1111)=1000，所以我们的和应该加上1111，但是1111不是最小的x，1009是一个质数，phi(1009) = 1008 > 1000，同样满足条件，所以我们这儿应该取1009而不是1111，着就能发现上述算法的问题了。但是我们怎么去找一个满足条件的最小x呢，首先明确一点对于x一定是大于这个数本身的。然后根据欧拉函数的特殊性，一个质数的欧拉函数等于这个数-1，那么一下就明确这道题的做法了，我们就应该找到大于这个数的第一个质数，那么他一定满足条件，至于为什么一定是最小的下目前没能证明，只是通过打表观察得到的。

代码

#include<bits/stdc++.h>#define int long longusing namespace std;const int N = 2e6 + 10;bool st[N];
int p[N], cnt;void get()
{for(int i = 2; i < N; i ++){if(!st[i]) p[cnt++] = i;for(int j = 0; p[j]*i < N; j ++){st[i*p[j]] = 1;if(i % p[j] == 0) break;}}
}void solve(int op)
{int n;cin >> n;int sum = 0;for(int i = 1; i <= n; i ++){int x;cin >> x;int ip = upper_bound(p, p+cnt, x) - p;sum += p[ip];}//Case 1: 22 Xukhacout << "Case " << op << ": "  << sum << " Xukha" << endl;
}signed main()
{int _;get();cin >> _;for(int i = 1; i <= _; i ++)solve(i);return 0;
}