[原创]codeforces 710D Two Arithmetic Progressions [同余方程]【数论】

2016-08-24 17:32:54 Tabris_ 阅读数：695

博客爬取于2020-06-14 22:43:42
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/52302558

题目链接：http://codeforces.com/problemset/problem/710/D
--------------------------.
D. Two Arithmetic Progressions
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
You are given two arithmetic progressions: a1k + b1 and a2l + b2. Find the number of integers x such that L ≤ x ≤ R and x = a1k’ + b1 = a2l’ + b2, for some integers k’, l’ ≥ 0.

Input
The only line contains six integers a1, b1, a2, b2, L, R (0 < a1, a2 ≤ 2·109, - 2·109 ≤ b1, b2, L, R ≤ 2·109, L ≤ R).

Output
Print the desired number of integers x.

Examples
input
2 0 3 3 5 21
output
3
input
2 4 3 0 6 17
output
2
-----------------------------.
题目大意 ：
就是给你a1, b1, a2, b2, L, R 在区间L~R找一个x 使得a1k’ + b1 = a2l’ + b2 问能找到的x的个数

解题思路 ：
根据题意 很明显的同余方程
x= b1 (mod a1)；
x= b2 (mod a2)；
然后解得x的最小正整数解之后 每次加上 lcm(a1,a2) 一直从l到r 这部分直接计算就能够得出
值得注意的是l与 b1,b2 的大小有关 在计算的时候l应取三者最大值;
Ps:题目很坑的是有负数的情况 也是赛后看了题解才知道。。

附本题代码
-----------------------------------.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
# include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef long long ll;
const int mod = 1000000007;
const int maxn = 200010;

LL exgcd(LL a,LL b,LL &x,LL &y)
{
    if(!b)
    {
        x=1,y=0;
        return a;
    }
    else
    {
        LL r = exgcd(b,a%b,x,y);
        LL t = x;
        x = y;
        y = t - (a/b) * y;
        return r;
    }
}
LL labs(LL a)
{
    if(a<0) return -a;
    else    return a;
}
int main()
{
    ios::sync_with_stdio(false);
    LL a1,a2,b1,b2,l,r;
    while(cin>>a1>>b1>>a2>>b2>>l>>r)
    {
        LL x,y;
        LL d = exgcd(a1,a2,x,y);
        if((b2-b1)%d)
        {
            puts("0");
            continue;
        }
        x*=(b2-b1)/d;
        x=(x%labs(a2/d)+labs(a2/d))%labs(a2/d);

       LL cnt = x*a1+b1;
       LL tmp = labs(a1*a2/d);
       LL ans = 0;
       l = max(l,max(b1,b2));
       if(l>r)
       {
           puts("0");
           continue;
       }
       if(cnt<=r) ans+=(r-cnt)/tmp+1;
       if(cnt<l)  ans-=(l-1-cnt)/tmp+1;
       printf("%I64d\n",ans);
    }
    return 0;
}