51nod1262 扔球

相关讨论里的答案：（by mint_my ）

1.反弹n次，那起点S，每次反弹点，终点S共连接n+1条边，那么原问题变为从S走n+1条边回到S,为令n=n+1
2.设步长为a条边，gcd（a，n）==1时，lcm（a,n）=a*n,由于a*n=n*a那么最少走n次步长为a的路线才能重合到S；反之gcd（a,n）==d时，lcm（a,n）=a*n/d,由于关系a*(n/d)=n*(a/d),最少走n/d步即反弹n/d-1<n次就可以回到S，所以根据题意，方案数为与边互质的数的个数即n的欧拉函数

#include<cstdio>

#include<cstring>

#include<cctype>

#include<algorithm>

using namespace std;

#define rep(i,s,t) for(int i=s;i<=t;i++)

#define dwn(i,s,t) for(int i=s;i>=t;i--)

#define clr(x,c) memset(x,c,sizeof(x))

#define ll long long

int main(){

	int n;scanf("%d",&n);++n;

	int ans=n;

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

		if(n%i==0) ans=ans/i*(i-1);

		while(n%i==0) n/=i;

	}

	if(n!=1) ans=ans/n*(n-1);

	printf("%d\n",ans);

	return 0;

}

1262 扔球

基准时间限制：1 秒空间限制：131072 KB 分值: 80 难度：5级算法题

关注

在圆上一点S，扔出一个球，这个球经过若干次反弹还有可能回到S点。N = 4时，有4种扔法，如图：

恰好经过4次反弹回到起点S（从S到T1，以及反向，共4种）。

给出一个数N，求有多少种不同的扔法，使得球恰好经过N次反弹，回到原点，并且在第N次反弹之前，球从未经过S点。

Input

输入一个数N(1 <= N <= 10^9)。

Output

输出方案数量。

Input示例

Output示例