题解 P2674 【《瞿葩的数字游戏》T2-多边形数】

lukelin · 2019-07-09 16:01:44 · 题解

前言

更好的阅读体验:
   我的博客

题解

这道题目我是按表格中的列来考虑的，

设读入的数字为x，考虑上面的表格。
我们发现如果当前为第k列，那么该列每行之间都差了1+2+\dots+(k-1)。
于是我们暴力枚举列号，如果当前的x满足(x-k)\ \%\ (1+2+\dots+(k-1))=0的话,
显然x是珂以成为一个多边形数的。
设它为n边形，那么显然n=(x-k)\ /\ (1+2+\dots+(k-1))+2
然后我们发现每一个边形数的第一个都是它自己，因此除了2以外不会有poor,特判一下即可。
还有一个1也需要特殊处理，它应该输出3和4。

代码

#include <cstdio> 

int read(){
    int x = 0; int zf = 1; char ch = ' ';
    while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
    if (ch == '-') zf = -1, ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); return x * zf;
}

int main(){
    int ng = read();
    while (ng--){
        int x = read(), ans1 = 0, ans2 = 0;
        if (x == 1){puts("3 4"); continue;}
        else if (x == 2){puts("Poor2"); continue;}
        /*n边形数  k + (n - 2) * (1 + 2 + ... + k)*/
        long long sum = 1;
        for (int k = 2; ; ++k){
            if (sum + k > x) break;
            int lft = x - k;
            if (!(lft % sum)){
                int ans = lft / sum + 2;
                if (ans >= 3){
                    if (ans < ans1 || (!ans1))
                        ans2 = ans1, ans1 = ans;
                    else if (ans < ans2 || (!ans2))
                        ans2 = ans;
                }
            }
            sum += k; 
        }
        if (ans1) printf("%d", ans1);
        if (ans2) printf(" %d\n", ans2);
        else puts("");
    }
    return 0;
}