Problem Description

Friend number are defined recursively as follows.

(1) numbers 1 and 2 are friend number;

(2) if a and b are friend numbers, so is ab+a+b;

(3) only the numbers defined in (1) and (2) are friend number.

Now your task is to judge whether an integer is a friend number.

 

Input

There are several lines in input, each line has a nunnegative integer a, 0<=a<=2^30.

 

Output

For the number a on each line of the input, if a is a friend number, output “YES!”, otherwise output “NO!”.

 

Sample Input

3

13121

12131

 

Sample Output

YES!

YES!

NO!
 
思路： 设c是Friend数，题中给出公式ab+a+b。则c=ab+a+b。c+1=ab+a+b+1=(a+1)*(b+1),所以推断n+1是否满足这个公式就可以。又由于1,2是最小的Friend数。

所以推断n+1=(a+1)^x*(b+1)^y即n+1=2^x*3^y是否成立。
 
 
代码：
 

#include<stdio.h>

int main()

{

	int n,x,y;

	while(scanf("%d",&n)!=EOF)

	{

		n+=1;//n先加1；

		x=0;y=0;

		while(n%2==0)

		{

			n=n/2;

			x++;

		}

		while(n%3==0)

		{

			n=n/3;

			y++;

		}

		if(n==1&&(x>0||y>0))//n=0时不是Friend数。

		printf("YES!\n");

		else

		printf("NO!\n");

	}

	return 0;

}