问题 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;
}