首页 > ACM题库 > HDU-杭电 > HDU 1719 Friend-递推-[解题报告] C++
2013
12-21

HDU 1719 Friend-递推-[解题报告] C++

Friend

问题描述 :

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.

输入:

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

输出:

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

样例输入:

3
13121
12131

样例输出:

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;

#include <iostream>
using namespace std;

int main()
{
	int n, x, y;
	while (~scanf ("%d", &n))
	{
		n++;
		x = y = 0;
		while (n % 2 == 0)
			n /= 2, x++;
		while (n % 3 == 0)
			n /= 3, y++;
		if (n == 1 && (x > 0 || y > 0))
			puts ("YES!");
		else puts ("NO!");
	}
	return 0;
}

 

解题报告转自:http://blog.csdn.net/a601025382s/article/details/9813151


  1. Thanks for taking the time to examine this, I really feel strongly about it and love studying a lot more on this topic. If possible, as you acquire experience

  2. 有两个重复的话结果是正确的,但解法不够严谨,后面重复的覆盖掉前面的,由于题目数据限制也比较严,所以能提交通过。已更新算法