调手表
题目描述
小明买了块高端大气上档次的电子手表，他正准备调时间呢。
在 M78 星云，时间的计量单位和地球上不同，M78 星云的一个小时有n nn分钟。
大家都知道，手表只有一个按钮可以把当前的数加一。在调分钟的时候，如果当前显示的数是0 00，那么按一下按钮就会变成1 11，再按一次变成2 22。如果当前的数是n − 1 n-1n−1，按一次后会变成0 00。
作为强迫症患者，小明一定要把手表的时间调对。如果手表上的时间比当前时间多1 11，则要按n − 1 n-1n−1次加一按钮才能调回正确时间。
小明想，如果手表可以再添加一个按钮，表示把当前的数加k kk该多好啊…
他想知道，如果有了这个+ k +k+k按钮，按照最优策略按键，从任意一个分钟数调到另外任意一个分钟数最多要按多少次。
注意，按+ k +k+k按钮时，如果加k kk后数字超过n − 1 n-1n−1，则会对n nn取模。
比如，n = 10 , k = 6 n=10, k=6n=10,k=6的时候，假设当前时间是0 00，连按2 22次+ k +k+k按钮，则调为2 22。
输入描述
一行两个整数n , k n, kn,k（0 < k < n ≤ 10 5 0 < k < n \leq 10^50<k<n≤105），意义如题。
输出描述
输出一行一个整数，表示按照最优策略按键，从一个时间调到另一个时间最多要按多少次。
输入输出样例
示例
输入
5 3输出
2样例解释
如果时间正确则按0 00次。否则要按的次数和操作系列之间的关系如下：
- 1 11：+ 1 +1+1
- 2 22：+ 1 , + 1 +1, +1+1,+1
- 3 33：+ 3 +3+3
- 4 44：+ 3 , + 1 +3, +1+3,+1
运行限制
- 最大运行时间：1 11s
- 最大运行内存:256 256256M
题目分析
题目可以转化为在模 n 的环上，从 0 出发，用 +1 和 +k 两种操作，求最远能几步到达某个数
把环看成一个图，每一次调试（+1 或者 +k）代价相同，遍历图将模 n 的环看成一个有 n 个节点的图，每个节点表示一个余数 0∼n−1。
从节点 x 出发，可以走到：
( x + 1 ) m o d n (x+1)\mod n(x+1)modn
( x + k ) m o d n (x+k)\mod n(x+k)modn
每条边表示一次操作（+1 或 +k），代价均为 1
这其实是用 BFS 按层遍历图，计算最短距离
代码
#include<iostream>#include<queue>#include<cstring>usingnamespacestd;constintN=100010;intdist[N];intmain(){intn,k;cin>>n>>k;memset(dist,-1,sizeof(dist));queue<int>q;dist[0]=0;q.push(0);while(!q.empty()){intcur=q.front();q.pop();// 两种操作：+1 和 +kintnext1=(cur+1)%n;intnextk=(cur+k)%n;if(dist[next1]==-1){dist[next1]=dist[cur]+1;q.push(next1);}if(dist[nextk]==-1){dist[nextk]=dist[cur]+1;q.push(nextk);}}// 找到最大值intmaxDist=0;for(inti=0;i<n;i++){maxDist=max(maxDist,dist[i]);}cout<<maxDist<<endl;return0;}
