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

　　题意：题目给出一个欧拉函数值F（X），让我们求>=这个函数值的最小数N，使得F（N） >= F(X);

　　分析：这个题目有两种做法。第一种，暴力打出欧拉函数表，然后将它调整成有序的，再建立一个新的表格记录满足条件的最小的欧拉值。

　　第二种，根据欧拉函数的性质，针对一个素数N，F（N） = N-1; 然后假设第一个大于N的素数为M，它的函数值为M-1，这时，在（N，M）之间的任何一个数都是合数，并且他们的欧拉值一定小于M-1，所以我们要找到题目中要求的最小数，可以从比它大一的数开始找，直到找到第一个素数为止，这个数就是我们要找的最小值。

　　注意：C++编译器不支持%I64，只支持%lld，我因为这个WA了几次，要注意编译器的要求和题目上方的说明。

　　代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define maxn 1500100
#define LL long long
LL prime[maxn+100];
void make()
{
    memset(prime,1,sizeof(prime));
    prime[1] = 0;
    for(int i = 2; i <= maxn; i++)
    {
        if(prime[i])
        {
            for(int j = i*2; j <= maxn; j += i)
            {
                prime[j] = 0;
            }
        }
    }
}
int main()
{
    LL t,n,num,ca = 0;
    make();
    LL sum;
    scanf("%lld",&t);
    while(t--)
    {
        scanf("%lld",&n);
        sum = 0;
        for(int i = 0; i < n; i++)
        {
            scanf("%lld",&num);
            for(LL j = num+1; true; j++)
            {
                if(prime[j])
                {
                    // printf("the min one = %d
",j);
                    sum += j;
                    break;
                }
            }
        }
        printf("Case %lld: ",++ca);
        printf("%lld Xukha
",sum);
    }
    return 0;
}