P2674 《瞿葩的数字游戏》T2-多边形数 题解（评分：7.3）

· · 题解

前言

这是我的第一篇题解，一来就写蓝题

好家伙，这还是我做出的第一道蓝题呢！

解决

先上伪代码：

cin>>ng;
for(i=1;i<=ng;i++) cin>>n[i];
for(i=1;i<=ng;i++)
{
    （特判）
    for(j=3;j<=n[i];j++)
    {
        if(n[i]是j边形数) （输出细则）
    }
    cout<<endl;
}

1.特判

阅读题目，我们容易发现，任何大于等于 3 的正整数 n ，都必然是 n 边形数。同时 1 是 3 边形和 4 边形数比较特殊，建议特判。

所以只有 2 和非正整数需要特判Poor。只有 1 需要特判 3 和 4 。

2.输出细则

在循环到每一个 n[i] 的时候，定一个变量 pp 来计算 n[i] 已经输出的多边形数数量，并初始化为 0 。

每输出一次，pp+1。

当 pp 到达 2 的时候退出循环，输出换行，开始计算下一个 n[i] 。

3. （重点）N[i] 是不是 j 边形数

大多数人都是按照表格一列一列考虑的，但我按行考虑。

我们可以发现所有第 x 个 j 边形数，其数都是下面这一串数列的和：

1$ , $1+(j-2)$ , $1+2(j-2)$ , $1+3(j-2)$ , $1+4(j-2)$ …… $1+(x-1)(j-2)

这不就是等差数列求和公式吗！

该数列首项为 1 ，末项为 1+()(j-2)，项数为 x 。

所以你们就知道第 x 个 j 边形数是什么了：

(2+(x-1)*(j-2))*x/2

化简成以 x 为主元的一元二次式，

((j-2)*x^2+(4-j)*x)/2

这个式子如果等于 n[i],则 n[i] 是 j 边形数。

就是 ((j-2)*x^2+(4-j)*x)/2=n[i]

再次化简为以 x 为主元的一元二次方程：

(j-2)*x^2+(4-j)*x-2*n[i]=0

由于 j 和 n[i] 在当前循环中都是已知量，可以用一元二次方程求根公式算出 x。

如果 x 不是整数，会向下取整，那么 ((j-2)*x^2+(4-j)*x)/2 不等于 n[i] ，我们就能得出 n[i] 不是 j 边形数。

如果 x 是整数，那么 ((j-2)*x^2+(4-j)*x)/2=n[i] ，我们就能得出 n[i] 是 j 边形数。

综上所述，我们可以在时间复杂度为 O(1) 中算出 n[i] 是不是 j 边形数。

所以最后代码（已经AC）如下:

#include<bits/stdc++.h>
using namespace std;
long long ng,n[101],i,j,x,pp; 
int main()
{
    cin>>ng;
    for(i=1;i<=ng;i++) cin>>n[i];
    for(i=1;i<=ng;i++)
    {
        pp=0;
        if(n[i]<1||n[i]==2)
        {
            cout<<"Poor"<<n<<endl;
            continue;
        }
        if(n[i]==1)
        {
            cout<<"3 4"<<endl;
            continue;
        } //特判1，2，非正整数。
        for(j=3;j<=n[i];j++)
        {
            x=(j-4+(long long)(sqrt((4-j)*(4-j)+8*(j-2)*n[i])))/2/(j-2);    //根据n[i]和j计算当前项数x。
            if(x*((j-2)*x-j+4)/2==n[i]) //根据x和j反推是否等于n[i],即验证n[i]是不是j边形数。
            {
                cout<<j<<" ";
                pp++;
                if(pp==2) break;
            }
        }
        cout<<endl;
    }
   return 0;
}