Open ManuShi98 opened 3 years ago
https://manushi98.github.io/2018/05/26/UVA%20-%2013250%20Balance%20Game(%E6%89%A9%E5%B1%95%E6%AC%A7%E5%87%A0%E9%87%8C%E5%BE%97)/
思路我们要解的一个方程是ax+by+cz=w。显然枚举是O(n^3)会超时，生成函数无法解决x,y,z是负数的情况。注意到m的范围只有5000，所以考虑将方程转化为ax+by=w-cz然后枚举z(-5000,5000)再跑extgcd。由于x(res/gcds)+kb/gcds,y(res/gcds)-ka/gcds都属于[-m,m]，我们能得到两个k的范围，它们的交集长度的累加就是答案。
https://manushi98.github.io/2018/05/26/UVA%20-%2013250%20Balance%20Game(%E6%89%A9%E5%B1%95%E6%AC%A7%E5%87%A0%E9%87%8C%E5%BE%97)/
思路我们要解的一个方程是ax+by+cz=w。显然枚举是O(n^3)会超时，生成函数无法解决x,y,z是负数的情况。注意到m的范围只有5000，所以考虑将方程转化为ax+by=w-cz然后枚举z(-5000,5000)再跑extgcd。由于x(res/gcds)+kb/gcds,y(res/gcds)-ka/gcds都属于[-m,m]，我们能得到两个k的范围，它们的交集长度的累加就是答案。