专栏文章

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

sskimlight
P12888题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mip1p3op
此快照首次捕获于
2025/12/03 04:43
3 个月前
此快照最后确认于
2025/12/03 04:43
3 个月前
查看原文

题意简述

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

思路

我们假设 KK 次移动中有 aa 次顺时针移动， bb 次逆时针移动，那么指针最后的位置可以表示为 ((a−b)+1) mod N((a-b)+1) \bmod N，又因为 a+b=Ka+b=K，所以我们将式子转化为： ((2a−(b+a))+1) mod N=(2a−K+1) mod N=((2a−K) mod N)+(1 mod N)((2a-(b+a))+1) \bmod N=(2a-K+1) \bmod N=((2a-K) \bmod N)+(1 \bmod N)。
注意到上式中只有 (2a−K) mod N(2a-K) \bmod N 是变量，所以 (2a−K) mod N(2a-K) \bmod N 的不同余数的个数就是最终答案。很容易可以得到 2a−K2a-K 的取值范围是 −K(a=0)-K(a=0) 到 K(a=K)K(a=K)，并且步长为 22。
分类讨论后发现 (2a−K) mod N(2a-K) \bmod N 的不同余数的个数与步长 22 和 NN 的最大公约数有关。
  • 如果 gcd⁡(2,N)=1\operatorname{gcd}(2, N)=1（即 NN 是奇数），序列 (2a−K) mod N(2a-K) \bmod N 会覆盖所有可能的余数，最多为 min⁡(K+1,N)\operatorname{min}(K+1, N)。
  • 如果 gcd⁡(2,N)=2\operatorname{gcd}(2, N)=2（即 NN 是偶数），序列 (2a−K) mod N(2a-K) \bmod N 会覆盖所有同奇偶的余数，最多为 min⁡(K+1,N/2)\operatorname{min}(K+1, N/2)。

代码

CPP
#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;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...