原题题号：1574

• 题目描述

ADA Ⅱ型数是指能表达成p^2与q^3两者之乘积的整数，p和q均大于1且不相等。72=2^3*3^2, 是最小的ADA Ⅱ型数。给定一个整数n，判定其是否为ADA Ⅱ型数。

• 输入

少于4000行数据组成，每行一个整数n（0<n<2^31）。

• 输出

每个整数n对应一行输出，如果是ADA Ⅱ型数，则输出一行YES，否则输出一行NO。

• 样例输入

1
72

• 样例输出

NO
YES
这题要是打模拟会TLE，应该先打表，再直接查询输出，这里使用set（集合）可以节省代码量，难度不大。代码如下：

#include <iostream>
#include <cstdio>
#include <set>
using namespace std;
int main()
{
    int n;
    set<int> s;
    for (int i = 2; i <= INT32_MAX / (i * i);i++)
        for (int j = 2;j*j<=INT32_MAX/(i*i*i); j++)
        if(i!=j)
            s.insert(i * i * i * j * j);
 
        while (cin >> n)
        {
            if(s.find(n)!=s.end())
                cout << "YES" << endl;
            else
                cout << "NO" << endl;
        }
    //system("pause");
    return 0;
}

本文作者：TTQ
本文链接：https://blog.ponder.fun/archives/21.html
最后修改时间：2020-02-09 12:30:51
本站未注明转载的文章均为原创，并采用 CC BY-NC-SA 4.0 授权协议，转载请注明来源，谢谢！