description
给定 \(0\leq a_1,a_2\leq 2*10^9, -2*10^9\leq b_1,b_2,L,R \leq 2* 10^9\)
求 \(\sum\limits_{x=\max(L,b1,b2)}^R [a_1\mid x-b_1][a_2\mid x-b_2]\)
solution
不妨设 \(L=\max(L,b1,b2)\)。
把原式化为 \(\sum\limits_{x=\lfloor\frac{L-1-b_1}{a_1}\rfloor+1}^{\lfloor\frac{R-b_1}{a_1}\rfloor} [a_2\mid a_1x+b1-b2]\)
也就是求方程 \(a_1x-a_2t=b_2-b_1\) 在 \([\lfloor\frac{L-1-b_1}{a_1}\rfloor+1,\lfloor\frac{R-b_1}{a_1}\rfloor]\) 上解的数量。
使用 exgcd 求解即可。
hint
我做这道题的时候的难点在于正确地写对 exgcd。花了超级长的时间调。
有以下需要注意的地方:
-
c++ 的除法是向零取整，也就是说不能正确处理负数向下取整。所以要手写 floor 函数。
-
如果 exgcd 的参数是负数，计算 \(y\) 时 \(a\) 除以 \(b\) 直接按照 c++ 的向零取整就可以了。
-
本题参数 \(-a_2\) 可以改成 \(a_2\)，可以简化解未知数。
qaq 感觉根本不会 exgcd
code
参考代码:Submission #222525953 - Codeforces
标签：lfloor,frac,CF710D,exgcd,leq,rfloor,b1 From： https://www.cnblogs.com/FreshOrange/p/17688935.html