Goodbye(博弈)
发布日期:2021-05-08 16:30:28 浏览次数:26 分类:精选文章

本文共 1301 字,大约阅读时间需要 4 分钟。

为了解决这个问题,我们需要分析给定整数n,两名玩家轮流选择一个特定的数字。第一个玩家选择一个因子,接下来的每一回合,玩家选择之前选出的数的其中一个因子。无法选择的玩家将获胜。我们的目标是判断先手是否能获胜,如果能,输出他选择的第一个数;否则输出-1。如果先手无法选择任何因子,输出0。

方法思路

  • 质因数分解:首先,我们需要分解给定的整数n,找出所有质因数及其指数。
  • 判断质因数数量:如果n有多个不同的质因数,先手无法获胜,输出-1。
  • 幂次分析:如果n是质数的幂次,计算其幂次长度。如果幂次长度为奇数,先手获胜,输出n;否则,输出-1。
  • 特殊情况处理:如果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,返回一个向量,包含所有质因数及其对应的指数。
  • 主函数:读取输入,处理每个测试用例。对于每个n,判断其是否为质数的幂次,并根据幂次长度判断先手是否能获胜。
  • 条件判断:根据质因数的数量和幂次长度,输出相应的结果。质因数数量大于1则输出-1,幂次长度为奇数则输出n,否则输出-1。
  • 上一篇:小破队的五一训练总结
    下一篇:Flower

    发表评论

    最新留言

    路过,博主的博客真漂亮。。
    [***.116.15.85]2025年05月06日 21时13分47秒