1.题目描述
小Q的数学老师给了小Q一个整数N,问小Q能否将N分解为两个整数X和Y相乘,并且满足X为奇数,Y为偶数,即能否找到奇数X和偶数Y满足X*Y=N。
小Q被这个问题难住了,希望能你来帮助他计算。
- 输入描述:
输入的第一行包含一个正整数t(1<=t<=1000),表示测试样例数。
接下来的t行,每行一个正整数N(2<=N<2^63),表示给出的N。保证N不是2的幂次。 - 输出描述:
如果能找到这样的X,Y,则依次输出X,Y,如果有多解输出Y最小的那组解,以空格分割,否则输出"No"。 - 输入示例:
2 10 5 - 输出示例:
5 2 No
2.题目解析
- 如果能够拆成奇数和偶数的乘积，那么这个数只能是偶数。
- 遍历所有小于
N的偶数，N整除偶数，结果是奇数，这两个数就是结果；反之，不存在。
3.参考答案
#include <bits/stdc++.h>
using namespace std;
int main() {
int t; // 测试样例数
scanf("%d", &t);
while(t--) {
long long n = 0;
scanf("%lld", &n);
if(n & 1) printf("No\n"); // 奇数直接为No
else {
long long x = 0; // 奇数
long long y = 0; // 偶数
for(y = 2; y <= n; y += 2) {// 遍历所有小于n的偶数
if(n % y == 0 && ((n / y) & 1)) { // 被偶数y整除并且结果是奇数。
x = n / y;
break;
}
}
printf("%lld %lld\n", x, y);
}
}
return 0;
}
