2017年上海金马五校程序设计竞赛：Problem I : Frog's Jumping

迈不过友情╰ 2022-06-13 23:48 154阅读 0赞

### Problem I : Frog's Jumping ###

From: [DHUOJ, 2017060309][DHUOJ_ 2017060309]

Submit (Out of Contest)

Time Limit: 1 s

--------------------

## 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.

![Dx1SLCzuRx_frog.jpg][]

## 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

题目意思：有0,1,2,3，，，，n-1个荷叶，然后青蛙从0开始每次走（k+x）%n步数，x为当前荷叶的下标，然后走n次，并且不能走到原来的走过的地方，问，输入一个n，有多少种小于n符合题目要求的N的个数。

然后也就是找规律，就是如果这个数是n的约数的，一定会走到曾经走过的地方，因为如果是约数，那么这个数乘一个小于N的数肯定能等于n的倍数。所以在走n次之内一定会走原来的地方，所以把所有次数找出来减去这个就是所求答案。

#include<iostream>
    #include<stdio.h>
    #include<string.h>
    using namespace std;
    int vis[1000005];
    int main()
    {
        int n;
        while(scanf("%d",&n)!=EOF)
        {
            memset(vis,0,sizeof(vis));
            int s=0;
            for(int i=2;i<=n/2;i++)
            {
                   if(n%i==0)
                    {
                        for(int j=i;j<n;j+=i)
                        {
                            if(vis[j]==0)
                            {
                                vis[j]=1;
                                s++;
                            }
                        }
                    }
            }
            if(vis[n]==0)
                s++;
            cout<<n-s<<endl;
        }
        return 0;
    }

[DHUOJ_ 2017060309]: http://acm.dhu.edu.cn/dhuoj
[Go]: http://lib.csdn.net/base/go
[Dx1SLCzuRx_frog.jpg]: http://acm.dhu.edu.cn/images/DHUOJ/RBVKlhF3qw/Dx1SLCzuRx_frog.jpg