codeforces 710D Two Arithmetic Progressions(线性同余方程)

题目链接：

http://codeforces.com/problemset/problem/710/D

分析：给你两个方程 a₁k + b₁ and a₂l + b₂，求在一个闭区间【L，R】中有多少个X，X满足 x = a₁k' + b₁ = a₂l' + b₂。

由此可以发现这两个方程满足线性同余，即 x ≡b1mod(a1) 且 x≡b2mod(a2); 也就是 a₁k' + b₁ = a₂l' + b_2a.

所以 a1k1 + (-a2k2) = (b2 - b1),由同余方程得： X ≡ (b2 - b1) mod(a2).

所以我们可以先求的一个特解x0,然后找到它的最小整数解 x,再把x 放在【L，R】里找出它包含多少个。

对于解线性同余方程：

求特殊解

对于线性同余方程

ax ≡ b (mod n) (1)

若 d = gcd(a, n)，d 整除 b ，那么b/d为整数。由裴蜀定理，存在整数对 (r,s) （可用辗转相除法求得）使得 ar+sn=d，因此 x0=rb/d是方程 (1) 的一个解。其他的解都关于n/d与 x 同余。即x≡x0+(n/d)*t (mod n) (0≤t≤d-1)。

举例来说，方程

12x ≡ 20 (mod 28)

中 d = gcd(12,28) = 4 。注意到 4 = 12 *(-2)+28*1，因此 x0≡5*(-2)≡-10≡4(mod 7)是一个解。对模 28 来说，t=1,x≡4+(28/4)*1≡11 (mod 28)；t=2,x≡4+(28/4)*2≡18 (mod 28)；t=3,x≡4+(28/4)*3≡25 (mod 28) 。所有的解就是 {4,11,18,25} 。

附：取模运算

int mod(int a,int b)
{
if(a >= 0)
return a % b;
else
return a % b + b;
}

线性同余方程

对于方程 a*x+b*y=n；有整数解得充分必要条件是（n %（a，b）==0），这个定理这里就不证明了，数论书上都有。

所以方程 a*x+b*y=n；我们可以先用扩展欧几里德算法求出一组x0，y0。也就是a*x0+b*y0=（a，b）；然后两边同时除以（a，b），再乘以n。这样就得到了方程a*x0*n/（a，b）+b*y0*n/（a，b）=n；我们也就找到了方程的一个解。

还有一个定理：若（a，b）=1，且x0，y0为a*x+b*y=n的一组解，则该方程的任一解可表示为：x=x0+b*t，y=y0-a*t；且对任一整数t，皆成立。（这个证明比较简单，就不写了）

这样我们就可以求出方程的所有解了，但实际问题中，我们往往被要求去求最小整数解，所以我们就可以将一个特解x，t=b/（a，b），x=(x%t+t）%t；就可以了。

 /*************************************************************************

     > File Name: cf710D.cpp

     > Author:

     > Mail:

     > Created Time: 2016年08月27日 星期六 22时28分30秒

  ************************************************************************/

 #include<iostream>

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 ll exgcd(ll a, ll b, ll& x, ll& y)

 {

     ll d = a;

     if(b!=)

     {

         d = exgcd(b,a % b,y,x);

         y -= (a / b) * x;

     }

     else

     {

         x = ;

         y = ;

     }

     return d;

 }

 int main()

 {

     ll a1,b1,a2,b2,L,R;

     cin >> a1 >> b1 >> a2 >> b2 >> L >> R;

     ll x,y;

     ll d = exgcd(a1,a2,x,y);

     if((b2 - b1) % d != )

     {

         cout <<  << endl;

         return ;

     }

     x *=(b2 - b1)/d;

     ll t = a2/d;

     x = (x % t + t) %t;

     ll cnt = a1 * x + b1;

     ll lcm = a1/d *a2;

     ll ans = ;

     L = max(L,max(b1,b2));

     if(L > R)

     {

         cout <<  << endl;

         return ;

     }

     if(cnt <= R) ans += (R-cnt)/lcm +;//放在区间里找包含多少个解，需要注意方式

     if(cnt < L) ans -= (L-cnt- )/lcm +;

     cout << ans << endl;

     return ;

 }

巴特西

codeforces 710D Two Arithmetic Progressions(线性同余方程)

求特殊解

最新文章

热门文章