2013
11-12

Candy Distribution

N children standing in circle who are numbered 1 through N clockwise are waiting their candies. Their teacher distributes the candies by in the following way:

First the teacher gives child No.1 and No.2 a candy each. Then he walks clockwise along the circle, skipping one child (child No.3) and giving the next one (child No.4) a candy. And then he goes on his walk, skipping two children (child No.5 and No.6) and giving the next one (child No.7) a candy. And so on.

Now you have to tell the teacher whether all the children will get at least one candy?

The input consists of several data sets, each containing a positive integer N (2 ≤ N ≤ 1,000,000,000).

For each data set the output should be either "YES" or "NO".

2
3
4

YES
NO
YES

//* @author: 82638882@163.com
/*题目大意：有n个同学坐成一个圆，一老师发糖果，依次发给第1、2、4、7...个同学，问是否每个同学都能得到至少一个糖。
*分析：写个朴素的程序，输出1~100的情况后不难发现，只有当n=2^k（k为整数）时，输出YES。
*/

import java.util.Scanner;
public class Main
{
public static void main(String[] args)
{
Scanner in=new Scanner(System.in);

while(in.hasNext())
{
int a=in.nextInt();
while(a%2==0)
a=a/2;
if(a==1) System.out.println("YES");
else System.out.println("NO");
}
}
}

1. 可以参考算法导论中的时间戳。就是结束访问时间，最后结束的顶点肯定是入度为0的顶点，因为DFS要回溯