f586 - 數字D×D
題目描述
題目要求將輸入的數字進行質因數分解，並根據分解結果進行分類。如果數字為 1，則輸出 1。如果數字沒有平方數因數，則輸出 (-1)^k，其中 k 是質因數的個數。否則，輸出 0。
解題思路
對於每個輸入數字 n，首先檢查是否為 1。如果是，則輸出 1。否則，嘗試從 2 開始迭代到 sqrt(n)，並進行質因數分解。在分解過程中，記錄質因數的個數。如果發現某個質因數出現了兩次或更多次（即存在平方數因數），則直接輸出 0。如果質因數分解完成且沒有發現平方數因數，則根據質因數的個數 k，輸出 (-1)^k。
複雜度分析
- 時間複雜度: O(sqrt(n))
- 空間複雜度: O(1)
程式碼
#include <iostream>
#include <cmath>
using namespace std;
int n,v;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> n;
for(int i=0;i<n;++i){
cin >> v;
if(v==1){
cout << "1\n";
}
else{
int ans=0,z=1;
for(int j=2;j<=sqrt(v)&&z;++j){
if(v%j==0){
++ans;
v/=j;
}
if(v%j==0){
z=0;
}
}
if(z){
if(ans%2){
cout << "1\n";
}
else{
cout << "-1\n";
}
}
else{
cout << "0\n";
}
}
}
}