现在的位置: 首页 > 综合 > 正文

HDU1719

2014年09月05日 ⁄ 综合 ⁄ 共 1189字 ⁄ 字号 评论关闭

Friend

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1689    Accepted Submission(s): 835


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!
 

题意:

①1,2都是friend数

②如果a,b都是friend数,那么ab+a+b也是friend数

任务:判断一个数n是不是friend数 (0<=n<=2^30)

 

设a, b都是friend数,

那么可以生成一个friend数 x = ab+a+b = (a+1)(b+1)-1

设c, d都是friend数,

那么可以生成一个friend数 y = (c+1)(d+1)-1

由x,y又可以生成friend数n = (x+1)(y+1)-1

代入得:n = [(a+1)(b+1)][(c+1)(d+1)]-1

1,2生成的是 (1+1)(2+1)-1;

1,1生成的是 (1+1)^2 - 1;

2,2生成的是 (2+1)^2 - 1;

由递归理解可知friend数n = [(1+1)^x * (2+1)^y] - 1;

AC code:

#include <iostream>
using namespace std;
int main()
{
	int n;
	while(cin>>n)
	{
		if(n==0){
			cout<<"NO!"<<endl;
			continue;
		}
		n++;
		while(n%2==0||n%3==0)
		{
			if(n%2==0)
				n/=2;
			if(n%3==0)
				n/=3;
		}
		if(n==1)
			cout<<"YES!"<<endl;
		else
			cout<<"NO!"<<endl;
	}
	return 0;
}

抱歉!评论已关闭.