Problem I : Frog's Jumping
Description
There are n lotus leaves floating like a ring on the lake, which are numbered 0, 1, ..., n-1 respectively. The leaf 0 and n-1 are adjacent.
The frog king wants to play a jumping game. He stands at the leaf 0 initially. For each move, he jumps k (0 < k < n) steps forward. More specifically, if he is standing at the leaf x, the next position will be the leaf (x + k) % n.
After n jumps, he wants to go through all leaves on the lake and go back to the leaf 0 finally. He can not figure out how many different k can be chosen to finish the game, so he asks you for help.
Input
There are several test cases (no more than 25).
For each test case, there is a single line containing an integer n (3 ≤ n ≤ 1,000,000), denoting the number of lotus leaves.
Output
For each test case, output exactly one line containing an integer denoting the answer of the question above.
Sample Input
4 5
Sample Output
2 4
Author: handoku
题意就是青蛙每次跳k,然后下一个位置是(当前位置+k)% n ,问你怎么选k才能使青蛙把所有的数都跳了一遍之后再返回0位置
若n和k有约数,那么一定要他们的约数的整数倍的地方是没有办法走到的(即n和k没有公约数 即互质)。
显然 只需要计算这个数n的欧拉函数即可。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int main(){
int n,i,temp;
while(scanf("%d",&n)!=EOF)
{
temp=n;
for(i=2;i*i<=n;i++)
{
if(n%i==0)
{
while(n%i==0) n=n/i;
temp=temp/i*(i-1);
}
if(n<i+1)
break;
}
if(n>1)
temp=temp/n*(n-1);
printf("%d\n",temp);
}
return 0;
}