循环题解

1016-标题统计

【题目描述】

凯刚写了一篇美妙的作文，请问这篇作文的标题中有多少个字符？

注意： 标题中可能包含大、小写英文字母、数字字符、空格和换行符。统计标题字符数时，空格和换行符不计算在内。

• 输入描述： 输入文件只有一行，一个字符串 。
• 输出描述： 输出文件只有一行，包含一个整数，即作文标题的字符数（不含空格和换行符）。

【解题思路】

可以利用 cin >> char 会自动跳过空格和换行符的特点，直接进行循环计数，直到文件末尾。

#include <bits/stdc++.h>
using namespace std;

int main() 
{
    int cnt = 0;
    char c;
    while (cin >> c) cnt++;
    cout << cnt;
    return 0;
}

1030-Game

【题目描述】

Nancy 喜欢博弈！Johnson 和 Nancy 得到了一个神奇的多重集合，仅包含一个正整数 ，两个人轮流进行操作。

一次操作可以将集合中一个数字分解为它的任意两个非 1 的因数，并加入集合中。当谁无法执行此步操作时，对方获胜。

在两人绝顶聪明的情况下，如果 Nancy 先手，请问最后的败者是谁？

• 输入描述： 第一行一个整数 (n)。()。
• 输出描述： 一个字符串，表示最后的败者（Johnson 或 Nancy）。

【算法分析】

1. 本质拆解： 每次操作将一个合数拆成两个因数，实际上是在增加集合中因数的个数。当集合中全是质数时，无法再拆分，游戏结束。

2. 游戏步数： 假设 的质因数总个数为 （包含重复的质因数，例如 ，）。

   • 初始状态集合有 个数。
   • 每操作一次，集合里的数字总数会 （去掉 个合数，增加 个因数）。
   • 最终状态集合有 个质数。
   • 总步数 。

3. 胜负判定：

• 若总步数 为奇数，先手 Nancy 走最后一步，后手 Johnson 输，Nancy 赢。
• 若总步数 为偶数，后手 Johnson 走最后一步，先手 Nancy 输。

【代码实现】

利用数学原理：一个合数 必定有一个不超过 的质因子。

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;

// 计算质因数个数 k
ll countprimefactors(ll n) {
    ll count = 0;
    for (ll i = 2; i * i <= n; i++) {
        while (n % i == 0) {
            count++;
            n /= i;
        }
    }
    if (n > 1) count++; // 处理大于 sqrt(n) 的最后一个质因子
    return count;
}

int main() {
    ll n;
    cin >> n;
    
  	ll k = countprimefactors(n)-1;//k轮
    // 如果k为偶数，Nancy(先手)必败，故败者是 Nancy；反之是 Johnson。
    // 注意：题目问的是“败者”
    if (k>0&&k%2==1)cout << "Johnson";
	else cout << "Nancy";
    return 0;
}