题解 P3951 【小凯的疑惑】

#### 一种图论的理解方法: 同余类最短路. 令 $a<b$, 然后将所有的数按照对$a$取模的余数分成$a$个剩余类. 每个同余类看成一个点, 即 {$p[0], p[1], ..., p[a-1]$}. 设$f[i]$为第$i$类数中最小的可以被表示出来的数, 则 $f[i]=k*a+i$. 由于$a<b$， 对$i>0$来说, $k$一定大于$0$ (当$k=0$时$f[i]=i<a$, 显然不能被表示出来). 而每一个$f[i]$都是由一个别的什么数加上$b$得到的(在模$a$意义下且$a$, $b$互质). 所以就可以从点$i$($0<=i<a$)向点$(i+b)$%$a$连一条长度为b的有向边(意味着加上$b$得到下一个数)， 然后就能转移了! 显然$f[0]=0$, 那么从$0$开始跑一个单源最短路, 球出每个剩余类中最小的可以被表示出来的数. 可是, 球了这个有什么猫用吗?? 如果$f[i]$是每个剩余类中最小的可以被表示出来的数, 那$f[i]-a$不就是最大的不能被表示出来的数吗! 可以理解成每个剩余类中的数都是$i+a$, $i+2*a$, $...$, 这样排列的($i>0$时). 假设求出来的$f[i]=i+x*a$, 那么之后的所有数都可以由它加上若干个$a$得出. 因此$i$+($x-1$)*$a$就是最大的不能被表示的数了. 在所有的$f[i]-a$($i>0$)里取最大就是答案. 但是这题只让写两行代码, 怎么跑最短路??还不如打个循环暴力 于是手动模拟一波跑最短路的过程: 每个点都只有一条出边, $0$->($b$%$a$)->($2*b$%$a$)->...->(($a-1$)*$b$%$a$)->$0...$ 形成了一个环. 这个很明显吧, 因为$a,b$互质. 所以最大的$f[i]$就是$f$[($a-1$)*$b$%$a$]. 边权都是 $b$ , 所以$f$[($a-1$)*$b$%$a$]=($a-1$)*$b$, 再减去一个$a$ 就得到了那个简短而凝聚着人类智慧结晶的公式: $a*b-a-b$ 代码: ```cpp #include<iostream> #include<cstdio> using namespace std; int main() { long long a,b; cin>>a>>b; cout<<a*b-a-b; } ```