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

题目传送门

思路

显然，每一次操作过后 $x$ 便会变成自己的一个因数，所以不妨将每次操作都看成，将 $x$ 变为一个小于自身且不等于 $1$ 的因数。

由于要求操作次数最大，所以每次操作过后，$x$ 都应该尽量大。所以操作时，我们要将 $x$ 变成其最大的非自身的因数，而这个数正是 $x$ 除以它的最小质因子。所以我们将 $x$ 依次除以自己的质因子，直到 $x$ 为 $1$ 或一个质数（因为这时，$y$ 无论取多少，$\gcd (x,y)$ 都等于 $1$）即可。

举个例子，当 $x=18$ 时，先将其分解质因数，$18=2\times 3^2$。我们先将 $18$ 和 $18÷2$ 即 $9$ 进行 $\gcd$ 变成 $9$，再和 $9÷3$ 进行 $\gcd$ 变成 $3$，然后就无法进行操作，最大操作次数为 $2$，容易证明没有更好的方案。

所以当询问类型为一时，答案为 $x$ 所有质因子的指数相加再减一（因为 $x$ 最终可能为它的一个质因子，所以要减一）,但是要特判 $x=1$ 的情况要直接输出 $0$，否则将输出 $-1$，因为 $1$ 没有质因子。

而当询问类型为二时，根据上面的结论，答案的所有质因子的指数相加过后应当等于 $q+1$，又因为要求答案最小，所以答案的质因子只能为 $2$，所以答案为 $2^{q+1}$。需要注意的是，$q$ 最大为 $62$，结果要使用 unsigned long long 存储。

代码

#include <bits/stdc++.h>
using namespace std;
int t,tp,x;
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&tp,&x);
        if(tp==1){
            if(x==1){//特判
                puts("0");
                continue;
            }
            int sum=0;
            for(int i=2;i*i<=x;i++)
                while(x%i==0)
                    sum++,x/=i;
            if(x>1)
                sum++;//统计质因子指数相加的数量
            printf("%d\n",sum-1);
        }else{
            printf("%llu\n",(unsigned long long)1<<x+1);//注意答案的大小会爆long long
        }
    }
    return 0;
}