AC代碼

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

題意：

求在[L,R]之間有多少個(gè)整數(shù)K滿足K=a1x+b1=a2y+b2，其中x,y為自然數(shù)，即是正數(shù)

題解：

很容易想到將等式移項(xiàng)，變?yōu)閍1x+a2(?y)=b2?b1

那么很明顯可以用擴(kuò)歐來求出一組x,y的特解，并將特解移至自然數(shù)范圍內(nèi)的最小解

因?yàn)樵绞堑仁?，接下來我們只需要關(guān)注其中一個(gè)解，例如x

設(shè)擴(kuò)歐求出的x的通解為x0+k×dx，其中dx=a2/gcd，因?yàn)樘亟鈞0是摸dx下最小自然數(shù)解，所以k也為自然數(shù)。

題目要求的是[L,R]之間有多少個(gè)整數(shù)K滿足K=a1x+b1

將通解代入，即求[L,R]之間有多少個(gè)整數(shù)K滿足K=(a1dx)k+a1x0+b1

那么最后就是求有多少k能讓整數(shù)落于[L,R]，因?yàn)閗連續(xù)，

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

寫成公式就是?R?(a1x0+b1)a1dx???L?(a1x0+b1)a1dx?+1

但要注意可能會(huì)除出來負(fù)數(shù)，因?yàn)閗為自然數(shù)，所以必須? k>=0