
Goodbye(博弈)
质因数分解:首先,我们需要分解给定的整数n,找出所有质因数及其指数。 判断质因数数量:如果n有多个不同的质因数,先手无法获胜,输出-1。 幂次分析:如果n是质数的幂次,计算其幂次长度。如果幂次长度为奇数,先手获胜,输出n;否则,输出-1。 特殊情况处理:如果n等于1,先手无法选择任何因子,输出0。 质因数分解函数: 主函数:读取输入,处理每个测试用例。对于每个n,判断其是否为质数的幂次,并根据幂次长度判断先手是否能获胜。 条件判断:根据质因数的数量和幂次长度,输出相应的结果。质因数数量大于1则输出-1,幂次长度为奇数则输出n,否则输出-1。
发布日期:2021-05-08 16:30:28
浏览次数:26
分类:精选文章
本文共 1301 字,大约阅读时间需要 4 分钟。
为了解决这个问题,我们需要分析给定整数n,两名玩家轮流选择一个特定的数字。第一个玩家选择一个因子,接下来的每一回合,玩家选择之前选出的数的其中一个因子。无法选择的玩家将获胜。我们的目标是判断先手是否能获胜,如果能,输出他选择的第一个数;否则输出-1。如果先手无法选择任何因子,输出0。
方法思路
解决代码
#include#include #include #include using namespace std;vector factorize(int n) { vector factors; if (n <= 1) return factors; for (int i = 2; i * i <= n; ++i) { if (n % i == 0) { factors.push_back(i); int exponent = 0; while (n % i == 0) { exponent++; n /= i; } factors.push_back(exponent); } } if (n > 1) { factors.push_back(n); factors.push_back(1); } return factors;}int main() { cout.tie(0); int t; while (t--) { int n; cin >> n; if (n == 1) { cout << 0 << endl; continue; } vector factors = factorize(n); if (factors.size() > 1) { cout << -1 << endl; } else { int exponent = factors[0]; int k = exponent + 1; if (k % 2 == 1) { cout << n << endl; } else { cout << -1 << endl; } } }}
代码解释
factorize
函数用于分解给定的整数n,返回一个向量,包含所有质因数及其对应的指数。