湛江专业网站建设,重庆住房建设工程信息网官网,成都定制app开发,怀集建设房管部门网站文章目录 题意:思路:代码 题意:
就是给你n个数#xff0c;对于每一个数y你都需要找到一个最小x使得 ϕ ( x ) ≥ y \phi(x) \ge y ϕ(x)≥y#xff0c;然后再求一个最小平和。
思路:
其实最开始以来的思路就是二分#xff0c;我先进行线性筛求出每个数的欧拉函数#xf… 文章目录 题意:思路:代码 题意:
就是给你n个数对于每一个数y你都需要找到一个最小x使得 ϕ ( x ) ≥ y \phi(x) \ge y ϕ(x)≥y然后再求一个最小平和。
思路:
其实最开始以来的思路就是二分我先进行线性筛求出每个数的欧拉函数然后二分去找到第一个大于等于a[i]的欧拉函数看起来确实挺合理的但是题目要求我们找到最小满足条件的x不是最小满足条件的phi(x)。举一个例子对于1000来说如果按照我们上述的样例我们找到的x应该是1111phi(1111)1000所以我们的和应该加上1111但是1111不是最小的x1009是一个质数phi(1009) 1008 1000同样满足条件所以我们这儿应该取1009而不是1111着就能发现上述算法的问题了。但是我们怎么去找一个满足条件的最小x呢首先明确一点对于x一定是大于这个数本身的。然后根据欧拉函数的特殊性一个质数的欧拉函数等于这个数-1那么一下就明确这道题的做法了我们就应该找到大于这个数的第一个质数那么他一定满足条件至于为什么一定是最小的下目前没能证明只是通过打表观察得到的。
代码
#includebits/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, pcnt, 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;
}
