loj2314 「NOIP2017」小凯的疑惑[同余最短路or数论]

这题以前就被灌输了“打表找规律”的思想，所以一直没有好好想这道题，过了一年还不太会qwq。虽然好像确实很简单，但是还是带着感觉会被嘲讽的心态写这个题解。。。而且还有一个log做法不会。。。

法1：（一开始没看懂，后由hkk神仙教导ORZ）

因为$ax+by=k$如果无视$\{x,y\}$非负整数解的条件的话，显然由于$gcd(a,b)=1$，所以所有$k$都可以表出。那么依题意如果有$k$不可以表出，是因为受了题目非负整数解条件的限制，也就是$x<0,y<0$，又因为$x,y$不可能同时$<0$，所以就是要求$x,y$异号表出的最大$k$。不妨让$a$项的$x$为负，那么为了保证$x,y$所有的通解都是一正一负，必定可以得出最后取模简化后必须要有$a\in (-b,0),b\in (0,a)$（由扩欧得到，不在这个范围也可以取模得到）。为了最大，$x$必须为$-1$，$b$项必须为$a-1$，这样就可以保证$k$最大了。

所以$k=-a+(a-1)b=ab-a-b$。

法2：（同余类最短路）

有关同余类最短路我在这里写了一下，这里就不啰嗦了。然后根据这个原理，假设$a<b$，设$f[i]$表示$\min\{kb|kb\mod=i\}$，也就是最小可以用$b$的倍数表出的、模$a$余数为$i$的数。这个可以和套路一样建边跑最短路，最后按套路找$\max\{f[i]-a\}$就行了。但是这里数据规模很大。但是有一个特殊性质，$gcd(a,b)=1$，并且这个最短路实际就是从$f[0]$到$f[b\mod a]$到$f[2b\mod a]$，往后跑一条链......所以这个dis越跑越大，一直跑到$f[ab\mod a]=f[0]$发现没法松弛，终止。显然可证中间不会出现$f[kb\mod a]=f[0],k\in[1,a-1]$。那么可以直接得出结论在最后一次$f[(a-1)b\mod a]$的dis最大，因此答案就是$f[(a-1)b\mod a]-a=(a-1)b-a=ab-a-b$.

a,b=map(int,input().split())

print(a*b-a-b)

巴特西

loj2314 「NOIP2017」小凯的疑惑[同余最短路or数论]

最新文章

热门文章