题意:问在一个圆形的镜面里,从任意一点发出一个光源,经n次反射回到起点的情况数是多少。
解法:直接贴题解吧……
求1至N+1中与N+1互质的个数,即欧拉函数。
代码:
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<limits.h>
#include<time.h>
#include<stdlib.h>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#define LL long long using namespace std; int eular(int n)
{
int ret = 1;
for(int i = 2; i * i <= n; i++)
{
if(n % i == 0)
{
n /= i;
ret *= i - 1;
while(n % i == 0)
{
n /= i;
ret *= i;
}
}
}
if(n > 1)
ret *= n - 1;
return ret;
}
int main()
{
int T;
while(~scanf("%d", &T))
{
while(T--)
{
int n;
scanf("%d", &n);
printf("%d\n", eular(n + 1));
}
}
return 0;
}