首页 > 代码库 > codeforces 710D Two Arithmetic Progressions(线性同余方程)

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

2024-08-11 22:19:09   224人阅读

题目链接：

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

分析：给你两个方程 a1k + b1 and a2l + b2，求在一个闭区间【L，R】中有多少个X，X满足 x = a1k‘ + b1 = a2l‘ + b2。

  由此可以发现这两个方程满足线性同余，即 x ≡b1mod(a1) 且 x≡b2mod(a2); 也就是 a1k‘ + b1 = a2l‘ + b2a.

  所以 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；就可以了。

 1 /************************************************************************* 2     > File Name: cf710D.cpp 3     > Author:  4     > Mail:  5     > Created Time: 2016年08月27日 星期六 22时28分30秒 6  ************************************************************************/ 7  8 #include<iostream> 9 #include<bits/stdc++.h>10 using namespace std;11 typedef long long ll;12 13 ll exgcd(ll a, ll b, ll& x, ll& y)14 {15     ll d = a;16     if(b!=0)17     {18         d = exgcd(b,a % b,y,x);19         y -= (a / b) * x;20     }21     else22     {23         x = 1;24         y = 0;25     }26     return d;27 }28 29 int main()30 {31     ll a1,b1,a2,b2,L,R;32     cin >> a1 >> b1 >> a2 >> b2 >> L >> R;33     ll x,y;34     ll d = exgcd(a1,a2,x,y);35     if((b2 - b1) % d != 0)36     {37         cout << 0 << endl;38         return 0;39     }40     x *=(b2 - b1)/d;41     ll t = a2/d;42     x = (x % t + t) %t;43     ll cnt = a1 * x + b1;44     ll lcm = a1/d *a2;45     ll ans = 0;46     L = max(L,max(b1,b2));47     if(L > R)48     {49         cout << 0 << endl;50         return 0;51     }52     if(cnt <= R) ans += (R-cnt)/lcm +1;//放在区间里找包含多少个解，需要注意方式53     if(cnt < L) ans -= (L-cnt- 1)/lcm +1;54     cout << ans << endl;55     return 0;56 }

 

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


联系
我们