欧拉函数中的性质 Φ(p)=p-1,p为素数。所以这个题算是贪心+数论吧。每个Φ(p)=p-1;只要从p开始,找素数,那么一定有Φ(k)>=p-1;只有当p=k时,等号成立。
#include <iostream> #include <cstring> #include <string> #include <map> #include <set> #include <algorithm> #include <fstream> #include <cstdio> #include <cmath> #include <stack> #include <queue> using namespace std; const double Pi=3.14159265358979323846; typedef long long ll; bool isprime(int n) { ; ) return true; else { ;i<=sqrt(n);i++) { ) { flag=; break; } } if(flag) return true; else return false; } } int main() { ; while(t--) { ; while(n--) { scanf("%d",&a);a++; while(!isprime(a)) a++; sum+=a; } printf("Case %d: %ld Xukha\n",i,sum); i++; } ; }