hdu 5430 Reflect 求圆镜内反射N次回到出口的方法数 欧拉函数

题意：从镜面材质的圆上一点发出一道光线反射$N$次后首次回到起点。
问本质不同的发射的方案数。

题解：

为什么要k和(N+1)是最简分数呢。因为要求的是不重复的路径，也就是求的是到了出口后射出去，而不是又反射回来。30+360和30的结果是一样的，但不能算一种。。
代码一：

//author: CHC
//First Edit Time:    2015-09-05 19:38
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <limits>
using namespace std;
typedef long long LL;
const int INF = numeric_limits<int>::max();
const LL LL_INF= numeric_limits<LL>::max();

int main()
{
    int t,n;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        int cnt=0;
        for(int i=1;i<=n;i++){
            if(__gcd(i,n+1)==1)++cnt;
        }
        printf("%d\n",cnt);
    }
    return 0;
}

代码二：

//author: CHC
//First Edit Time:	2015-09-05 19:38
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <limits>
using namespace std;
typedef long long LL;
const int MAXN = 1000000+1000;
const int INF = numeric_limits<int>::max();
const LL LL_INF= numeric_limits<LL>::max();
LL phi[MAXN],prime[MAXN];
void getprime(){
    memset(prime,0,sizeof(prime));
    phi[1]=1;
    for(int i=2;i<MAXN;i++){
        if(!prime[i])prime[++prime[0]]=i,phi[i]=i-1;
        for(LL j=1,k;j<=prime[0]&&(k=prime[j]*i)<MAXN;j++){
            prime[i*prime[j]]=1;
            if(i%prime[j]==0){
                phi[k]=phi[i]*prime[j];
                break;
            }
            phi[k]=phi[i]*(prime[j]-1);
        }
    }
}
int main()
{
    getprime();
    int t,n;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        printf("%I64d\n",phi[n+1]);
    }
    return 0;
}