1370 - Bi-shoe and Phi-shoe(LightOJ1370)(数论基础，欧拉函数)

http://lightoj.com/volume_showproblem.php?problem=1370

欧拉函数：

在数论，对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目。

φ(n)=少于或等于n的数中与n互质的数的数目.

一会专门写一个关于欧拉函数的的博客  先来说这一道题

这道题是欧拉函数的反面

给你一个φ（n）然后求n;

所以这道题我感觉是找规律

n=(φ(n)+1的第一个素数）;

#include<stdio.h>

#include<string.h>

#include<math.h>

#include<algorithm>

#include<iostream>

#include<queue>

using namespace std;

#define N 1000005

int b[N];

int a[N];

void prime()

{

    memset(b,,sizeof(b));

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

    {

        if(b[i]==)

        {

            for(int j=i+i; j<N; j=j+i)

            {

                b[j]=;

            }

        }

    }

}

int main()

{

    int T,n,t=;

    scanf("%d",&T);

    prime();

    while(T--)

    {

        memset(a,,sizeof(a));

        scanf("%d",&n);

        long long int sum=;

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

        {

            scanf("%d",&a[i]);

            for(int j=a[i]+;j<N;j++)

            {

                if(b[j]==)

                {

                    sum+=j;

                    break;

                }

            }

        }

        printf("Case %d: %lld Xukha\n",t++,sum);

    }

    return ;

}