題目在 https://zerojudge.tw/ShowProblem?problemid=j242
這題基本是在求因數分解. 求出質因數和其指數後就可以算出a和b. 我用求質數的方式來做因數分解,
求質數可以看另一篇zerojudge b513. 判斷質數-商競103有詳細解釋. 為了加快速度, 每找到一個質因數,就把n除以它,這樣n會越來越小,避免不必要的計算.
vector <int> V; //V儲存所有質數
vector <int> N; //N儲存所有質數的指數
//測試v是否為質數
bool getNextPrime(int v){
int max=sqrt(v);
for(int i : V){
if(i>max) break;
if(v%i==0)
return false;
}
return true;
}
//當prime是n的質因數時, 求出prime的指數, 並把n除以prime後,變小return
int reduce(int n, int prime){
//把質因數放入V
V.push_back(prime);
//算指數count
int count=0;
while(n%prime==0){
count++;
n=n/prime;
}
//把指數放入N
N.push_back(count);
return n;
}
當質因數分解完成後,就可以計算a和b了. 因為a是開方後的數, 所以指數每減一次2, a就乘一個質因數. 指數減完若剩1, b就乘以質因數.
index=0;
int a=1;
int b=1;
for(int i : V){
//指數每減一次2, a就乘一個質因數i
while(N[index]>=2){
a=a*i;
N[index]-=2;
}
//指數減完若剩1, b就乘以質因數i
if(N[index]>0)
b=b*i;
index++;
}
//印出a
if(a>1) cout << a << " ";
//印出b
if(b>1) cout << "sqrt(" << b <<")" << endl;完整程式如下.
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
vector <int> V; //V儲存所有質數
vector <int> N; //N儲存所有質數的指數
//測試v是否為質數
bool getNextPrime(int v){
int max=sqrt(v);
for(int i : V){
if(i>max) break;
if(v%i==0)
return false;
}
return true;
}
//當prime是n的質因數時, 求出prime的指數, 並把n除以prime後,變小return
int reduce(int n, int prime){
//把質因數放入V
V.push_back(prime);
//算指數count
int count=0;
while(n%prime==0){
count++;
n=n/prime;
}
//把指數放入N
N.push_back(count);
return n;
}
int main(){
int n;
cin >> n;
//加入質因數2
int prime=2;
n=reduce(n,prime);
//加入質因數3
prime=3;
n=reduce(n,prime);
//加入更多質因數 6n-1, 6n+1
int max=sqrt(n);
int index=6;
while(index-1<=max){
//測試6n-1是否為質數
if(getNextPrime(index-1)){
//加入質因數6n-1
prime=index-1;
n=reduce(n,prime);
max=sqrt(n);
}
//測試6n+1是否為質數
if(getNextPrime(index+1)){
//加入質因數6n+1
prime=index+1;
n=reduce(n,prime);
max=sqrt(n);
}
index+=6;
}
//最後剩下的n若>1, 那n也是質數
if(n>1){
V.push_back(n);
N.push_back(1);
}
index=0;
int a=1;
int b=1;
for(int i : V){
//指數每減一次2, a就乘一個質因數i
while(N[index]>=2){
a=a*i;
N[index]-=2;
}
//指數減完若剩1, b就乘以質因數i
if(N[index]>0)
b=b*i;
index++;
}
//印出a
if(a>1) cout << a << " ";
//印出b
if(b>1) cout << "sqrt(" << b <<")" << endl;
}