b534 - 質因數、最大公因數
題目描述
題目要求對給定的兩個正整數 a 和 b，完成以下三個任務：
- 將
a進行質因數分解，並以指定格式輸出質因數乘積式。 - 計算
a和b的最大公因數 (GCD)。 - 判斷計算得到的 GCD 是否為質數，並輸出 "Y" 或 "N"。
解題思路
程式首先使用埃拉托斯特尼篩法預先計算出 65536 以內的質數。然後，對於每組輸入的 a 和 b，程式執行以下步驟：
- 質因數分解： 從 2 開始，迭代地找到
a的最小質因數，並將其分解出來，直到a變為 1。分解過程中，記錄每個質因數及其出現次數，並按照指定格式輸出。 - 最大公因數： 使用歐幾里得演算法 (輾轉相除法) 計算
a和b的最大公因數。 - 質數判斷： 檢查計算得到的 GCD 是否為質數。如果 GCD 大於 1 且在預先計算的質數表中為 0 (表示是質數)，則輸出 "Y"，否則輸出 "N"。
複雜度分析
- 時間複雜度: O(N * sqrt(M) + sqrt(M) + M)，其中 N 是輸入的數量，M 是 a 和 b 的最大值 (65536)。埃拉托斯特尼篩法的時間複雜度是 O(M log log M)，但在此處簡化為 O(M)。質因數分解的時間複雜度是 O(sqrt(M))，GCD 的時間複雜度是 O(log(min(a, b)))，質數判斷的時間複雜度是 O(1)。
- 空間複雜度: O(M)，主要用於儲存質數表。
程式碼
#include <iostream>
#include <cmath>
using namespace std;
int pri[65536]={1,1};
void p(){
for(int i=2;i<sqrt(65536);i++){
if(pri[i]==0){
for(int j=i*2;j<65536;j+=i){
if(pri[j]!=1)
pri[j]=1;
}
}
}
}
int GCD(int m,int n){
if(m%n==0)
return n;
else
return GCD(n,m%n);
}
int main(){
p();
int a,b,c,j,g;
cin >> a;
while(cin >> a >> c){
b=a;
for(int i=2;i<=b;i++){//20=2*2*5
if(a%i==0){
cout << i ;
a/=i;
for(j=1;a%i==0;j++)
a/=i;
if(j>1)
cout << "^" << j;
if(a!=i && a!=1)
cout << "*";
if(a==1)
cout << " , ";
}
}
if(a>c)
g=GCD(c,b);
else
g=GCD(b,c);
printf("%d , ",g);
if(pri[g]==0)
cout << "Y\n";
else
cout << "N\n";
}
}