AC代码

https://codeforces.com/contest/710/submission/176949038

题意：

求在[L,R]之间有多少个整数K满足K=a1x+b1=a2y+b2，其中x,y为自然数，即是正数

题解：

很容易想到将等式移项，变为a1x+a2(−y)=b2−b1

那么很明显可以用扩欧来求出一组x,y的特解，并将特解移至自然数范围内的最小解

因为原式是等式，接下来我们只需要关注其中一个解，例如x

设扩欧求出的x的通解为x0+k×dx，其中dx=a2/gcd，因为特解x0是摸dx下最小自然数解，所以k也为自然数。

题目要求的是[L,R]之间有多少个整数K满足K=a1x+b1

将通解代入，即求[L,R]之间有多少个整数K满足K=(a1dx)k+a1x0+b1

那么最后就是求有多少k能让整数落于[L,R]，因为k连续，

所以直接算不大于R的最大k和不小于L的最小k即可.

写成公式就是⌊R−(a1x0+b1)a1dx⌋−⌈L−(a1x0+b1)a1dx⌉+1

但要注意可能会除出来负数，因为k为自然数，所以必须  k>=0