题目描述

小凯手中有两种面值的金币，两种面值均为正整数且彼此互素。每种金币小凯都有无数个。在不找零的情况下，仅凭这两种金币，有些物品他是无法准确支付的。现在小凯想知道在无法准确支付的物品中，最贵的价值是多少金币？注意：输入数据保证存在小凯无法准确支付的商品。

输入描述:

输入数据仅一行，包含两个正整数 a 和 b，它们之间用一个空格隔开，表示小凯手中金币的面值。

输出描述:

输出文件仅一行，一个正整数 N，表示不找零的情况下，小凯用手中的金币不能准确支付的最贵的物品的价值。

示例1

输入
3 7
输出
11
说明
小凯手中有面值为3和7的金币无数个，在不找零的前提下无法准确支付价值为 1、2、4、5、8、11的物品，其中最贵的物品价值为11。
比11贵的物品都能买到，比如：
12 = 3 x 4 + 7 x 0
13 = 3 x 2 + 7 x1
14 = 3 x 0 + 7 x 2
15 = 3 x 5 + 7 x 0

备注

对于 30% 的数据：1 ≤ a,b ≤ 50;
对于 60% 的数据： 1 ≤ a,b ≤ 10,000;
对于 100% 的数据：1 ≤ a,b ≤ 1,000,000,000。

解答

一种图论的理解方法: 同余类最短路.

令 , 然后将所有的数按照对 取模的余数分成  个剩余类. 每个同余类看成一个点, 即 . 设  为第 类数中最小的可以被表示出来的数, 则  . 由于  ， 对 来说,  一定大于  (当  时  , 显然不能被表示出来). 而每一个 都是由一个别的什么数加上  得到的(在模  意义下且  互质). 所以就可以从点 向点 连一条长度为b的有向边(意味着加上  得到下一个数)， 然后就能转移了! 显然  , 那么从  开始跑一个单源最短路, 球出每个剩余类中最小的可以被表示出来的数.

可是, 球了这个有什么猫用吗??

如果  是每个剩余类中最小的可以被表示出来的数, 那  不就是最大的不能被表示出来的数吗! 可以理解成每个剩余类中的数都是  这样排列的(  时). 假设求出来的  , 那么之后的所有数都可以由它加上若干个  得出. 因此 就是最大的不能被表示的数了. 在所有的 里取最大就是答案.

但是这题只让写两行代码, 怎么跑最短路??还不如打个循环暴力

于是手动模拟一波跑最短路的过程: 每个点都只有一条出边, 形成了一个环. 这个很明显吧, 因为  互质. 所以最大的  就是 . 边权都是 , 所以  , 再减去一个 就得到了那个简短而凝聚着人类智慧结晶的公式: 

代码: 

#include<iostream>
#include<cstdio>
using namespace std;

int main()
{
    long long a,b;
    cin>>a>>b;
    cout<<a*b-a-b;
}


来源：matsuk