Bi-shoe and Phi-shoe

时间:2023-03-09 22:07:21
Bi-shoe and Phi-shoe

欧拉函数中的性质 Φ(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++;
     }
     ;
  }