演唱顺序问题
题目描述
2014“华为杯”南京邮电大学大学生团体歌唱大赛与2013年情况相似：大赛分为多轮，每一轮随机选择参赛团体进行两两PK赛。当根据多轮多场的PK赛成绩能够确定排名次序时，大赛结束。但对于去年的PK赛，有些参赛选手颇有微词，认为PK赛演唱顺序虽然通过抽签来公平决定，但是不能充分展示南邮作为中国IT精英摇篮的风采，建议2014年PK赛演唱顺序通过脑力决定，例如搞些智力抢答，最快做出回答正确的参赛团队优先决定自己的演唱顺序。
主办方认为PK赛演唱顺序通过脑力决定的想法值得尝试，于是决定在2014“华为杯”歌唱大赛采用以下方案是：主办方给参加PK赛的两个团队一个正整数K，请每一个团队从1开始按照规则变换到K，同时记录每次的变换代价，两个团队在完成变换后比较各自的变换总代价，变换总代价较小的团队优先决定自己的演唱顺序，如果两个团队的变换总代价相同，则主办方继续给两个团队下一个数字，直至变换总代价不同，其中变换规则描述如下：
Ø 从1开始进行变换，一直持续到获得K；
Ø 若M是变换中的当前数字，则你可以从M生成两个正整数A、B，这里M=A×B，然后你可以将A加到M获得一个新的数字A+M，而B是你这次变换的代价，B要累加先前已有变换的总代价中。
举一个例子，若K为9，则（1）1=1×1，所以1变换为1+1=2，累计总代价为1；（2）2=1×2，所以2变换为2+1=3，累计总代价为1+2=3；（3）3=3×1，所以3变换为3+3=6，累计总代价为1+2+1=4；（4）6=3×2，所以6变换为6+3=9，累计总代价为1+2+1+2=6。
我对主办方采用的上述方案很是困惑，想知道从1变换到N的总代价最小是多少，请你帮助解决这个问题。
输入
输入包括多个测试用例，首先给出测试用例数N，接着给出N个测试用例，每一个测试用例包括1行，给出一个正整数K，1≤N<1000000，1≤K≤5000000。
输出
针对每一个测试用例，输出一行，给出从1变换到N的最小总代价。
样例输入
2
9
20
样例输出
6
8
解题思路一
按照题意求出5000000以内的所有数字所需的代价。
1 const int INF = 0x3f3f3f3f; 2 int a[5000000]; 3 memset(a, INF, sizeof(a)); 4 a[0] = 0; 5 a[1] = 0; //输入数字为1时，所需代价为0 6 for(int i=2; i<=5000000; ++i) 7 { 8 for(int j=1; j<=i/2; ++j) 9 { 10 if(i%j == 0) 11 { 12 if(a[i]+i/j < a[i+j]) 13 { 14 a[i+j] = a[i]+i/j; 15 } 16 if(a[i]+j < a[i+i/j]) 17 { 18 a[i+i/j] = a[i]+j; 19 } 20 } 21 } 22 }
思路应该没有问题，可是超时了。因为每次都要求每个数的约数。然后再判断。
解题思路二
看了别人的代码和思路才AC。
x = a*b;
y = x+a; //由x转化为y的代价为b
y = a*(b+1)；每次求出当前数字m的最小质因子n，则由m/n转化为m的代价为n-1就是m/n转化为m的最小代价。每次求出最小的代价，然后求和得到最小的结果。
1 #include <stdio.h> 2 #include <string.h> 3 #include <cmath> 4 using namespace std; 5 6 const int maxn=5000005; 7 int a[maxn]; 8 9 int main() 10 { 11 int t; 12 scanf("%d", &t); 13 memset(a, 0, sizeof(a)); 14 for(int i=2; i<maxn; ++i) 15 { 16 if(a[i]) continue; 17 int j=a[i]=i; 18 while(j < maxn) 19 { 20 if(a[j] == 0) a[j] = i; 21 j = j+i; 22 } 23 } 24 while(t--) 25 { 26 int n; 27 int ans = 0; 28 scanf("%d", &n); 29 while(1 != n) 30 { 31 ans += (a[n]-1); 32 n = n-n/a[n]; 33 } 34 printf("%d ", ans); 35 } 36 return 0; 37 }