LightOJ 1370 Bi-shoe and Phi-shoe（欧拉函数）-白红宇

LightOJ 1370 Bi-shoe and Phi-shoe（欧拉函数）

阅读量：4839 次

发布时间：2019-06-11

本文共 852 字，大约阅读时间需要 2 分钟。

题意：

给一些数Ai（第 i 个数），Ai这些数代表的是某个数欧拉函数的值，我们要求出数 Ni 的欧拉函数值不小于Ai。而我们要求的就是这些 Ni 这些数字的和sum，而且我们想要sum最小，求出sum最小多少。

思路：

素数P的欧拉函数值为P-1。

所以对于一个给出的数，我们去寻找大于它的第一个素数即可。

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #include
             9 #include
             
              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

转载于:https://www.cnblogs.com/zyb993963526/p/6819446.html

你可能感兴趣的文章