UVa 516 Prime Land

题目描述题目定义了一种质数进制表示法每个大于111的整数xxx可以唯一表示为质数幂的乘积形式xp0e0⋅p1e1⋯pkek x p_0^{e_0} \cdot p_1^{e_1} \cdots p_k^{e_k}xp0e0​​⋅p1e1​​⋯pkek​​其中p0p1⋯pkp_0 p_1 \cdots p_kp0​p1​⋯pk​为质数ei≥1e_i \ge 1ei​≥1。输入给出若干行每行是某个正整数xxx2x≤327672 x \le 327672x≤32767的质数进制表示按pip_ipi​递减顺序每对pip_ipi​和eie_iei​用空格分隔。对于每个xxx输出x−1x-1x−1的质数进制表示同样按pip_ipi​递减顺序。输入以一行0结束。输入格式输入包含多行每行若干个整数表示pip_ipi​和eie_iei​交替出现pip_ipi​递减。最后一行是0。输出格式对于每个非零输入行输出一行表示x−1x-1x−1的质数进制表示格式与输入相同pip_ipi​递减每对之间用空格分隔。样例输入17 1 5 1 2 1 509 1 59 1 0输出2 4 3 2 13 1 11 1 7 1 5 1 3 1 2 1题目分析本题的核心是计算给定质数幂乘积表示的数减去111后的质因数分解。算法步骤从输入读取pip_ipi​和eie_iei​计算x∏pieix \prod p_i^{e_i}x∏piei​​。计算yx−1y x - 1yx−1。对yyy进行质因数分解得到质数及其指数。按质数降序输出。注意事项xxx最大为327673276732767可以直接使用整型计算。质因数分解时从222开始遍历质数直到y\sqrt{y}y​或yyy变为111。输出时按质数降序排列。复杂度分析每组数据O(x)O(\sqrt{x})O(x​)分解可接受。代码实现// Prime Land// UVa ID: 516// Verdict: Accepted// Submission Date: 2016-08-08// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintMAX_N33000;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intprimes[MAX_N1]{0},prime_count0,factors[16][2],factor_count;primes[prime_count]2;for(inti3;iMAX_N;i2)if(primes[i]0){for(intj2*i;jMAX_N;ji)primes[j]-1;primes[prime_count]i;}string line;while(getline(cin,line),line!0){intn1,p,e;istringstreamiss(line);while(isspe)n*pow(p,e);n--;factor_count0;memset(factors,0,sizeof(factors));for(inti0;iprime_countn1;i){if(n%primes[i]0){factors[factor_count][0]primes[i];factors[factor_count][1]1;n/primes[i];while(n1n%primes[i]0){factors[factor_count][1];n/primes[i];}factor_count;}}coutfactors[factor_count-1][0] factors[factor_count-1][1];for(intifactor_count-2;i0;i--)cout factors[i][0] factors[i][1];cout\n;}return0;}