「TPOI-1A」鞋子特大号 题解

· · 题解

签到题。

先看 1 询问：

分析一次操作，例如 2310 和 1890 进行操作。将两个数分解质因数得到，2310=2\times3\times5\times7\times11，1890=2\times3\times5\times7\times3\times3。操作完毕得到的数为 210=2\times3\times5\times7。可以看出，一次操作之后会将 x 的质因子至少删去一个。当所有因子只剩下一个时，不能再删了，即为不能操作。

那么为了尽可能多地操作，我们只需要保证一次删去一个质因子即可，那么记初始 x 的质因子个数为 n（例：2310=2\times3\times5\times7\times11，所以 n=5），那么最大操作次数显然是 n-1。

于是我们直接 \Theta(\sqrt n) 枚举出 x 的质因子个数即可。

再看 2 询问：

给定 q，求出一个最小的 x，使得 x 最多能进行恰好 q 次操作。

那么既然能进行 q 次操作，如果我们按最优方式操作，这个数一定只有 q+1 个质因子。为了让这个 x 最小，那么所有质因子也应该尽可能小。我们知道最小的质数为 2，所以这个询问的答案就是 2^{q+1}。\Theta(q) 计算即可。

最终的时间复杂度为 \Theta(T\sqrt{n})，可以通过本题。记得开 unsigned long long。

#include <bits/stdc++.h>
using namespace std;
bool isp(int x) {
    if(x <= 1) return false;
    for(int i = 2;i * i <= x;i++) {
        if(x % i == 0) return false;
    }
    return true;
}
int main() {
    int t; cin >> t;
    while(t--) {
        int opt,x; cin >> opt >> x;
        if(opt == 1) {
            int cnt = 0;
            for(int i = 2;i * i <= x;i++) {
                if(x % i == 0 && isp(i)) {
                    while(x % i == 0) {cnt++; x /= i;}
                    if(x == 1) {cnt--; break;}
                }
            }
            cout << cnt << endl;
        }
        else {
            unsigned long long p = 1;
            for(int i = 1;i <= x+1;i++) p *= 2;
            cout << p << endl;
        }
    }
    return 0;
}