臭不要脸地水了一波xdu校赛，一心暴力果断T，后来才差不多能看懂解释
题目链接：http://acm.xidian.edu.cn/problem.php?id=1290
题目描述
众所周知，汀老师是XDUACM实验室最优秀的人，无论是学习还是打游戏。今天他突然想到一个好玩的游戏。规则是这样的，在游戏中他要得到n个小国，初始的时候小国和小杰各有1个。经过了很久的修炼，汀老师学会了两种魔法，他每次可以动用自己的智慧来使用魔法。
第一个魔法：（小杰变小国）可以使用自己的智慧，复制和当前小杰一样数量的小国出来；
第二个魔法：（小国大爆发）可以将当前的小杰变成和小国的数量一样，然后小国的数量加倍！
因为汀老师的智力是无限多的，他不关心花掉的智力大小。但是好学的汀老师想尽快得到n个小国，使得能有更多的时间去读paper和打比赛。他想问问你，最少需要使用多少次魔法可以恰好得到n个小国。
得到了n个小国后，汀老师去学习，但是小国们基因突变在电脑里越来越多！他们来组织汀老师学习，现在告诉汀老师我要得到更多的同伴！
输入
多组数据，第一行一个正整数T(T<=100000)表示数据组数。
接下来T行，每行一个正整数n(n<=10^6)。
输出
对于每组数据输出一个整数，表示得到n个小国汀老师最少需要使用多少次膜法。
样例输入
2
1
3
样例输出
0
2
思路
很明显，对于任意n>1，代表小国和小杰数目的状态（n,m）可以由一个之前的状态通过一次魔法二和若干次魔法一得到（可以为零次）。
我们定义num[x]表示生成x个小国需要使用多少次魔法，假设x个小国的状态可以由一个之前的p个小国的状态经过1次魔法二和c(c>=0)次魔法一得到，则有
\[\begin{equation} num[x=(2+c)p] = num[p]+c+1 \end{equation}\]我们将1次魔法二和c次魔法一定义为一个基本变换，从初态到终态可以经过若干次基本变换得到，现在问题转换为如何控制基本变换的次数使得最终得到的num[x]最小。通过观察上面的式子我们可以发现求num[x]的过程其实是不断对x进行因式分解，设\(x=e_1e_2e_3 \dots e_k\) ，则有
\[\begin{equation} num[x]=\sum_{i=1}^k e_i-1 \end{equation}\]如何使得上式中的累加和最小，这时我们猜测因子能拆就拆最好，也就是拆成全是素因子（勉强把1也当成素数好了，反正它不影响结果），下面简单证明一下拆比不拆好。
设\(x=e_1e_2\)，不拆有\(num[x]=e_1e_2-1\)，拆有\(num[x]=e_1+e_2-2\)，两式相减得到：
\[\begin{equation} e_1e_2-1-(e_1+e_2-2)=e_1e_2-(e_1+e_2)+1=(e_1-1)(e_2-1)>=0 \end{equation}\]因此将x分解质因数，\(x=p_1^{\alpha_1}p_2^{\alpha_2}p_3^{\alpha_3} \dots p_k^{\alpha_k}\)，最终结果应该为
\[\begin{equation} ans_x=\sum_{i=1}^k\alpha_i(p_i-1) \end{equation}\]至于最后这道题是分解质因数还是像DP一样去递推就看个人喜好了。
另外有一个非常重要的问题，他这个题，卡cin！！！，T了不知道多少发，所以还是换成scanf好了。
贴两条代码 ：
//直接分解质因数算
#include <bits/stdc++.h>
using namespace std;
int cal (int n)
{
int ans=0, s=sqrt(n);
for (int i=2; i<=s; i++)
while (n%i == 0)
{
ans += i-1;
n /= i;
}
ans += n-1;
return ans;
}
int main ()
{
int n, t;
scanf ("%d", &t);
while (t--)
{
scanf ("%d", &n);
printf ("%d\n", cal(n));
}
return 0;
}
//DP的形式，利用最小质因数转移状态
#include <bits/stdc++.h>
using namespace std;
int f[1000001]={0};
bool is_p[1000001]={0};
vector<int> v;
int main ()
{
int t, n;
for (int i=2; i<=1000; i++) //质数筛 只需要筛出sqrt(n)范围的就可以了
{
if (!is_p[i])
v.push_back(i);
for (auto x:v)
if (x*i > 1000)
break;
else
is_p[x*i] = true;
}
for (int i=2; i<=1000000; i++) //时限问题，先预处理出来
{
f[i] = i-1; //先默认这是个质数
for (auto j:v) //找最小质因数转移状态
if (i%j == 0)
{
f[i] = f[i/j]+j-1;
break;
}
else if (j*j > i) break;
}
scanf ("%d", &t);
while (t--)
{
scanf ("%d", &n);
printf ("%d\n", f[n]);
}
return 0;
}