首页 > 代码库 > LightOJ 1370 Bi-shoe and Phi-shoe（欧拉函数）
LightOJ 1370 Bi-shoe and Phi-shoe（欧拉函数）
http://lightoj.com/login_main.php?url=volume_showproblem.php?problem=1370
题意：
给一些数Ai（第 i 个数），Ai这些数代表的是某个数欧拉函数的值，我们要求出数 Ni 的欧拉函数值不小于Ai。而我们要求的就是这些 Ni 这些数字的和sum，而且我们想要sum最小，求出sum最小多少。
思路：
素数P的欧拉函数值为P-1。
所以对于一个给出的数，我们去寻找大于它的第一个素数即可。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<vector> 6 #include<queue> 7 #include<cmath> 8 #include<map> 9 #include<stack>10 using namespace std;11 12 const int maxn=1e6+5;13 14 int n;15 int vis[maxn];16 17 void get_primes()18 {19 int m=sqrt(maxn+0.5);20 for(int i=2;i<=m;i++)21 {22 if(!vis[i])23 {24 for(int j=i*i;j<=maxn;j+=i)25 vis[j]=1;26 }27 }28 }29 30 int main()31 {32 //freopen("D:\\input.txt","r",stdin);33 int T;34 int kase=0;35 get_primes();36 scanf("%d",&T);37 while(T--)38 {39 long long sum=0;40 scanf("%d",&n);41 for(int i=0;i<n;i++)42 {43 int x;44 scanf("%d",&x);45 for(int k=x+1;;k++)46 {47 if(!vis[k])48 {49 sum+=k;50 break;51 }52 }53 }54 printf("Case %d: %lld Xukha\n",++kase,sum);55 }56 57 return 0;58 }
LightOJ 1370 Bi-shoe and Phi-shoe（欧拉函数）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。