LightOJ1370 Bi-shoe and Phi-shoe
发布时间:2020-12-14 04:20:57 所属栏目:大数据 来源:网络整理
导读:题意:给定一个数的欧拉函数的值,让你求最小的满足欧拉函数值的那个数字,然后求和。 思路:手动模拟一下样例2,发现满足条件的数字就是给定数字下一次出现的质数。 例如10,下一个质数是11;11,下一个质数是13,12,下一个是13,13,下一个是17依此类推。
题意:给定一个数的欧拉函数的值,让你求最小的满足欧拉函数值的那个数字,然后求和。 思路:手动模拟一下样例2,发现满足条件的数字就是给定数字下一次出现的质数。 例如10,下一个质数是11;11,下一个质数是13,12,下一个是13,13,下一个是17依此类推。 #include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int maxn = 1e6+10; int book[maxn]; void Init() { memset(book,1,sizeof(book)); for(int i = 2; i < maxn; i++) { if(book[i]) for(int j = 2*i; j < maxn; j += i) book[j] = 0; } } int main(void) { Init(); int t; scanf("%d",&t); for(int kase = 1; kase <= t; kase++) { long long sum = 0; int n; scanf("%d",&n); while(n--) { int m; scanf("%d",&m); for(int i = m+1; ;i++) { if(book[i]) { sum += i; break; } } } printf("Case %d: %lld Xukhan",kase,sum); } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |