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: [email protected]/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> */
/*题目大意：有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要回溯