W - 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.

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和b并不一定是不相同的

然後每次生成了新的friend數都要和之前的進行組合，在操作上我并沒有想出非常好的辦法。。。。。。

然後我嘗試從别的角度思考。在我看來，這些這麼強烈“數學味道”的題目，都可能要我們分析出其中的一些奧妙。

設c是一個friend數，然後c+a*b+a+b 其中a和b都是friend數

讓我們做一下變形（兩邊都加1）

有可能有很多同學和我一樣一開始覺得莫名其妙，為什麼要這樣子處理呢。。。。。。其實我就是觀察a*b+a+b這個式子，首先它有a*b這個交叉項，然後有三項，也就是說我們可以大膽的猜測，應該有一個類似（a+x)(b+x)這樣子的式子，是以我就猜想了一下可以兩邊都加一個1，這樣子保證了a、b這兩項系數不變。

如果想到了這裡，那麼我們其實已經解決了這個問題的絕大部分了。

首先我們可以根據這個式子

c+1=(a+1)*(b+1)

遞推一下，首先，a、b、c都是friend數，也就是說，這個式子是可以不斷延伸的，直到根源。

根源是什麼，我們的一開始題目給的1、2兩個friend數

也就是說c+1=2的n次方與3的m次方相乘

其中n和m都是大于等于0的正整數。

代碼展示：

#include<iostream>

using namespace std;

int main()

{

    int n=0;

    int m=0;

    while(cin>>m)

    {

        if(m==0)

        {

            cout<<"NO!"<<endl;

            continue;

        }

        n=m+1;

        while(n%2==0)

        n=n/2;

        while(n%3==0)

        n=n/3;

        if(n==1)

        cout<<"YES!"<<endl;

        else

        cout<<"NO!"<<endl;

    }

}

首先有幾點說明：

1、int可以滿足2的30次方，是以我選了int類型。

2、當輸入的數字是0的時候，需要進行特殊處理，要不然根據一開始的程式會輸出YES！然後注意是continue不是break！你後面還要輸入數字呢！-3-

嗯嗯，大概就是這麼多啦~歡迎大家一起來讨論~