LOJ 1370 Bi-shoe and Phi-shoe（欧拉函数的简单应用）

题目链接：http://lightoj.com/volume_showproblem.php?problem=1370

题意：给你n个整数，第i个整数为Xi。定义phi(k)为k的欧拉函数值，设pi为满足phi(pi)>=Xi的最小整数，题目就是要求sum(p1,p2,p3,...,pn)

思路：对任意x，有prime[i]<=x<prime[i+1]必定有EulerPhi[x]<=prime[i]，要满足phi(p)>=x那么p必定为x后面的第一个素数，进行素数打表即可。

code：

 #include <cstdio>

 #include <cstring>

 typedef long long LL;

 const int MAXN = ;

 int p[MAXN];

 bool isPrime[MAXN];

 void init()

 {

     memset(isPrime, true, sizeof(isPrime));

     isPrime[] = false;

     isPrime[] = false;

     // isPrime[1000001] = true;

     for (int i = ; i * i < MAXN; ++i) {

         if (isPrime[i]) {

             int j = i * i;

             while (j < MAXN) {

                 isPrime[j] = false;

                 j += i;

             }

         }

     }

     int k = ;

     for (int i = ; i >= ; --i) {

         if (isPrime[i]) {

             p[i] = k;

             k = i;

             continue;

         }

         p[i] = k;

     }

 }

 int main()

 {

     init();

     int nCase;

     scanf("%d", &nCase);

     for (int cas = ; cas <= nCase; ++cas) {

         int n, k;

         scanf("%d", &n);

         LL ans = ;

         for (int i = ; i < n; ++i) {

             scanf("%d", &k);

             ans += p[k];

         }

         printf("Case %d: %lld Xukha\n", cas, ans);

     }

     return ;

 }

巴特西

LOJ 1370 Bi-shoe and Phi-shoe（欧拉函数的简单应用）

最新文章

热门文章