题解：P12888 [蓝桥杯 2025 国 Java B] 钟楼管理员

skimlight · 2025-06-23 20:06:15 · 题解

题意简述

有一个钟表，表盘上是从 1 到 N 的连续整数，初始时指针指向 1。每次拨动指针，指针会移动一格，经过 K 次这样的随机拨动（可以顺时针也可以逆时针）后，指针可能指向多少个不同的数字？

注：表盘是环形！！！

思路

我们假设 K 次移动中有 a 次顺时针移动， b 次逆时针移动，那么指针最后的位置可以表示为 ((a-b)+1) \bmod N，又因为 a+b=K，所以我们将式子转化为： ((2a-(b+a))+1) \bmod N=(2a-K+1) \bmod N=((2a-K) \bmod N)+(1 \bmod N)。

注意到上式中只有 (2a-K) \bmod N 是变量，所以 (2a-K) \bmod N 的不同余数的个数就是最终答案。很容易可以得到 2a-K 的取值范围是 -K(a=0) 到 K(a=K)，并且步长为 2。

分类讨论后发现 (2a-K) \bmod N 的不同余数的个数与步长 2 和 N 的最大公约数有关。

• 如果 \operatorname{gcd}(2, N)=1（即 N 是奇数），序列 (2a-K) \bmod N 会覆盖所有可能的余数，最多为 \operatorname{min}(K+1, N)。

• 如果 \operatorname{gcd}(2, N)=2（即 N 是偶数），序列 (2a-K) \bmod N 会覆盖所有同奇偶的余数，最多为 \operatorname{min}(K+1, N/2)。

代码

#include <bits/stdc++.h>

#define int long long

using namespace std;

signed main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin >> T;
    while (T--) 
    {
        int n,k;
        cin >> n >> k;
        int ans;
        if(n%2==1)ans=min(k+1,n);
        else ans=min(k+1,n/2);
        cout << ans << '\n';
    }
    return 0;
}