HDU 1719 Friend(思考テーマ)

Friend
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2420 Accepted Submission(s): 1226
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!
構想:まずみんなは(a+1)*(b+1)=友好数+1を見ます;次に、各(友好数+1)が2または3の倍数であることが証明されています.これは、基礎の友好数が1と2であるため、a=b=1のときに3を得るのも友好数であり、1と2は5を得るのが友好数であり、それから下にいくつかの点を探すことができ、各友好数は(x+1)=(2^a)*(3^b)の形式で書くことができ、それから下に行けばいいことを証明することができます.次はACコードです.

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

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