HDU 1719 Friend
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. 1和2为朋友数
2. 如果有一个朋友数为，另一个为b，那么a*b+a+b也是朋友数
3. 满足上面的两个条件的所有情况都为朋友数
是朋友数输出“YES!”，不是输出“NO!”。
C++
/*&同为1为1，|同为0为0。假如a和b都为朋友数，那么可以通过a*b+a+b得到另一个朋友数c。我们可以将其列出来：
a*b+a+b = c; - (a+1)(b+1) = c+1;
a和b起初只有1和2。那么就可以看出来，一个朋友数c，加上1，肯定是2或3的倍数。输入一个数n，通过不断地对(n+1)除等3和2，最后如果得到的结果为1，那么就可以证明c为朋友数。
注意：0不为朋友数。*/
#include <iostream>
#include <stdio.h>
using namespace std;
int main()
{
int a;
while(~scanf("%d", &a))
{
if(a == 0)
{
cout << "NO!" << endl;
continue;
}
int t = a + 1;
while(t%2 == 0 || t%3 == 0)
{
if(t % 2 == 0)
{
t /= 2;
continue;
}
if(t % 3 == 0)
{
t /= 3;
continue;
}
}
if(t == 1)
cout << "YES!" << endl;
else
cout << "NO!" << endl;
}
return 0;
}
