UVa 516
題目
http://domen111.github.io/UVa-Easy-Viewer/?516
給一個數字 $X$ 質因數分解後式，求 $X-1$ 的質因數分解式
想法
可以利用 stringstream 讀取輸入，取得所有數值就可以拿到 $X$ 以及 $X’=X-1$
至於質因數分解的部分，我們可以藉由質數篩的過程當中紀錄每個數字第一次是被誰篩掉(也就是最小因數)
例如: 10 -> 2 9 -> 3 17 -> 17
如此一來，對於每個詢問 $X’$ 每次先找到最小因數 $p$ ，紀錄當前的值 $X’$ 可以被整除幾次，並且將 $X’$ 除以 $p$，直到 $X’$ 為 $1$ 的時候表示我們已經找完了
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
|
#include<iostream>
#include<sstream>
#include<cmath>
const int MaxN = 32768;
int fact[MaxN], ans[MaxN][2];
using namespace std;
string s;
bool fir;
int x,n,a,b,p,cnt,px;
int main(){
for(long long i=2 ; i<=MaxN ; i++){
if(!fact[i]){
fact[i]=i;
for(long long j=i*i ; j<=MaxN ; j+=i){
if(!fact[j]){
fact[j]=i;
}
}
}
}
while(getline(cin,s)){
if(s=="0") break;
fir=true; n=1; px=0;
stringstream ss;
ss<<s;
while(ss>>x){
if(fir) a=x;
else{
b=x;
n*=pow(a,b);
}
fir=!fir;
}
n--;
while(n!=1){
p=fact[n];
cnt=0;
while(n%p==0){
cnt++;
n/=p;
}
ans[px][0]=p;
ans[px][1]=cnt;
px++;
}
for(int i=px-1 ; i>=0 ; i--){
if(i!=px-1) cout<<" ";
cout<<ans[i][0]<<" "<<ans[i][1];
}
cout<<"\n";
}
return 0;
}
|
複雜度分析
質數篩的複雜度為 $O(NloglogN)$
每筆測資計算 $X$ 時間複雜度約為 $O(\Omega(X))$
每筆測資質因數分解時間複雜度約為 $O(\Omega(X))$
每筆測資輸出時間複雜度約為 $O(\Omega(X))$
其中， $\Omega(X)$ 表示 $X$ 的不同質因數個數。$\Omega(X)$ 表示 $X$ 的質因數個數
總時間複雜度約為 $O(NloglogN + 2\Omega(X) + \Omega(X))$