問題 B: 第N個智慧數

題目描述

一個正整數如果能表示成了兩個正整數的平方差，則稱這個數為“智慧數”，比如16就等于5的平方減去3的平方，是以16就是一個智慧數，從1開始的自然數列中，将“智慧數”從小到大編号為1,2,3，„„，n。現輸入一個正整數n，輸出第n個“智慧數”。

輸入

僅包含一個正整數 n（1≤n≤100）。

輸出

僅包含一個正整數，表示編号為 n 的智慧數。

樣例輸入

3

樣例輸出

7

思路：因式分解找到是否是智慧數的判斷條件

若滿足x=a²-b²=(a+b)*(a-b)則x是一個智慧數。

設a-b=i

則a+b最小為(i+1)+1=i+2 x=(i+2)*i=i²+2i

再往後是 (i+2)+(1+1)=i+4 x=(i+4)*i=i²+4i

(i+n)+n=i+2n x=(i+2n)*i=i²+2ni (n是大于0的整數)

對于任意大于0的i x=i²+2ni

若i為奇數 則ii為奇數 2ni為偶數，偶數+奇數=奇數 即所有i為奇數時的智慧數必定為奇數

若i為偶數 則ii為4的倍數 2ni為4的倍數 即所有i為偶數時的智慧數必定為4的倍數

當i=1時 x=1+2n 是以所有大于3的奇數全是智慧數

當i=2時 x=4+4n 是以所有大于8而且是4的倍數的都是智慧數

其實思考的思路是先證明出了大于3的奇數都是智慧數和大于8的4的倍數都是智慧數，然

後通過證明所有智慧數必定為奇數或者是4的倍數來證明不滿足上述條件的數都不是智慧

數。

綜上，若x為智慧樹，則一定滿足x為大于3的奇數或者x為大于8的四的倍數

#include<iostream>
using namespace std;
int main()
{
    int n;//p存大于3的奇數，q存大于8的4的倍數
    cin>>n;
    int p=3,q=8;
    int s=0,ans=0;
    while(s!=n)
    {
        if(p<q)
        {
            ans=p;
            p+=2;
            s++;
        }
        else
        {
            ans=q;
            q+=4;
            s++;
        }
    }
    cout<<ans<<endl;
    return 0;
}

           

每四個數分為一個區間，第一個區間[1,4]第二個[5,8]依次類推

把每個區間的智慧數記錄下來

{3}，{5,7,8}，{9,11,12}，{13,15,16}，{17,19,20} …

每個區間必定有兩個奇數和一個4的倍數

是以除了第一個區間之外的區間都有三個智慧數

是以前N(N>1)個區間的智慧數個數為:1+3*(N-1)

若第n個智慧數包含前N個區間的所有智慧數，N取最大值，r表示N區間之外的智慧數個數

N=(n-1)/3;

r=n-1-3*N;

若n等于0，則第n個智慧數恰為第N個區間的最後一個智慧數即N*4+4

若n=1，則n為第n+1個區間的第一個智慧數即(N+1)*4+1

若n=2，則n為第n+1個區間的第二個智慧數即(N+1)*4+3

#include<iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;
    if(n==1)
    {
        cout<<"3"<<endl;
    }
    else if(n==2)
    {
        cout<<"5"<<endl;
    }
    else  
    {
        int N,r;
        N=(n-1)/3;
        r=n-1-3*N;
        int a[3]={N*4+4,(N+1)*4+1,(N+1)*4+3};
        cout<<a[r]<<endl;
    }
    return 0;
}