企业官网建设流程全解析

题目描述

题目定义了一种质数进制表示法：每个大于111的整数xxx可以唯一表示为质数幂的乘积形式：
x=p0e0⋅p1e1⋯pkek x = p_0^{e_0} \cdot p_1^{e_1} \cdots p_k^{e_k}x=p0e0​​⋅p1e1​​⋯pkek​​
其中p0<p1<⋯<pkp_0 < p_1 < \cdots < p_kp0​<p1​<⋯<pk​为质数，ei≥1e_i \ge 1ei​≥1。输入给出若干行，每行是某个正整数xxx（2<x≤327672 < x \le 327672<x≤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后的质因数分解。

算法步骤

1. 从输入读取pip_ipi​和eie_iei​，计算x=∏pieix = \prod p_i^{e_i}x=∏piei​​。
2. 计算y=x−1y = x - 1y=x−1。
3. 对yyy进行质因数分解，得到质数及其指数。
4. 按质数降序输出。

注意事项

• 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//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;constintMAX_N=33000;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intprimes[MAX_N+1]={0},prime_count=0,factors[16][2],factor_count;primes[prime_count++]=2;for(inti=3;i<=MAX_N;i+=2)if(primes[i]==0){for(intj=2*i;j<=MAX_N;j+=i)primes[j]=-1;primes[prime_count++]=i;}string line;while(getline(cin,line),line!="0"){intn=1,p,e;istringstreamiss(line);while(iss>>p>>e)n*=pow(p,e);n--;factor_count=0;memset(factors,0,sizeof(factors));for(inti=0;i<prime_count&&n>1;i++){if(n%primes[i]==0){factors[factor_count][0]=primes[i];factors[factor_count][1]=1;n/=primes[i];while(n>1&&n%primes[i]==0){factors[factor_count][1]++;n/=primes[i];}factor_count++;}}cout<<factors[factor_count-1][0]<<' '<<factors[factor_count-1][1];for(inti=factor_count-2;i>=0;i--)cout<<' '<<factors[i][0]<<' '<<factors[i][1];cout<<'\n';}return0;}