P9063 [yLOI2023] 分解只因数
[yLOI2023] 分解只因数
题目描述
给定一个正整数 n，对 n 分解质因数。
设 n = p_1 × p_2 × p_3 × ... × p_x，其中 p_i 均为质数。
如果 p_i 均为奇数，则称 n 为『只因数』。
现在，给出若干个 n，请你判断 n 是不是『只因数』。
输入格式
本题单测试点内有多组测试数据。
第一行是一个整数，表示数据组数 T。
接下来 T 行，每行一个整数，表示一组数据的 。
输出格式
对每组数据，输出一行一个字符串。如果 n 是『只因数』，请输出 Yes，否则输出 No。
样例 #1
样例输入 #1
5
2
3
4
6
9
样例输出 #1
No
Yes
No
No
Yes
提示
数据规模与约定
本题共有 10 个测试点。对第 i 个测试点，T = max(1, i - 1)。
- 对 30% 的数据，n ≤ 3。
- 对 50% 的数据，n ≤ 10。
- 另有 10% 的数据，n 为奇数。
- 另有 10% 的数据，n 为偶数。
- 对 90% 的数据，n ≤ 10^9。
- 对 100% 的数据，1 ≤ T ≤ 9，2 ≤ n ≤ 10^18。
分析
这题可以用普通的思路求解，即老老实实地分解质因数然后再老老实实地判断每一个是否能被 2 整除。
但是我们要知道 2 是唯一的偶质数，所以只要判断 n 的质因数里有没有 2 即可。
但是思路其实还可以再简化。我们还知道因数中含有偶数的就是偶数，没有偶数的就是奇数；再看到上面的分析，可得『只因数』即质因数中含有 2 的数都是偶数，非『只因数』即质因数中不含有 2 的都是奇数。
到这里，这道看起来很有难度的题目就被简化成了判断奇偶数的问题。（这就是数学的力量吗）
下面的代码放的就是最终简化后思路的代码，一个简单的奇偶数判定。
但是还是要有温馨提示的：要用 long long ，笔者就在这里崩了好几次
提交答案
#include<bits/stdc++.h>
using namespace std;
int main(){
long long t, n; //一定要记得开long long！
cin >> t;
while(t--){
cin >> n;
if(n % 2 == 0){
cout << "No" << endl;
}else{
cout << "Yes" << endl;
} //只因数（奇偶数）判定
}
return 0;
}