C.调手表

C. 调手表

题目描述：

一块表，只有小时和分钟， $ n $ 为进制。每次只能够 $ +1 $ 或 $ +k $ ，从任意一个分钟调到另外任意一个分钟最少需要按多少次。

数据范围：
$ 0\lt k \lt n \le 10^5 $

题解：

因为所有的起点都是等价的，所以只需要求出从 $ 0 $ 开始到其他各个时间的就行。

使用 $ BFS $ 搜索，每个点有两种情况， $ +1 $ 或 $ +k $ ，第一次访问到的时候就是最短次数。取最大值就行。

代码：

using namespace std;
using namespace FAST_IO;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e5 + 10;
const int maxm = 1e5 + 10;
int t, n, m, k;
queue<int> q;
int cnt[maxn];
int ans = 0;
void bfs()
{
    q.push(0);
    cnt[0] = 0;
    while (!q.empty())
    {
        auto out = q.front();
        q.pop();
        int v = (out + 1) % n;
        if (!(v == out || cnt[v] != 0 || v == 0))
        {
            cnt[v] = cnt[out] + 1;
            ans = max(ans, cnt[v]);
            q.push(v);
        }

        v = (out + k) % n;
        if (!(v == out || cnt[v] != 0 || v == 0))
        {
            cnt[v] = cnt[out] + 1;
            q.push(v);
            ans = max(ans, cnt[v]);
        }
    }
}
int main()
{
// #define COMP_DATA
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    // read(n, k);
    // dp[0] = 0;
    // int ans = 0;
    // for(int i = 1; i < n; i++)
    // {
    //     dp[i] = -1;
    // }
    // for(int i = 1; i < n; i++)
    // {
    //     if(dp[(i - k + n) % n] != -1)
    //     {
    //         dp[i] = min(dp[(i - k + n) % n], dp[(i - 1 + n) % n]) + 1;
    //     }
    //     else
    //     {
    //         dp[i] = dp[(i - 1 + n) % n] + 1;
    //     }
    //     printf("dp[%d]=%d\n", i, dp[i]);
    //     ans = max(ans, dp[i]);
    // }
    // cout << ans << endl;
    read(n, k);
    bfs();
    // for(int i = 0; i < n; i++)
    // {
    //     printf("cnt[%d]=%d\n", i, cnt[i]);
    // }
    cout << ans << endl;

    return 0;
}