Codeforces Problem 710D Two Arithmetic Progressions

Accept: 0 Submit: 0
Time Limit: 1 second Memory Limit : 256 megabytes

Problem Description

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·10^9,??-?2·10^9?≤?b1,?b2,?L,?R?≤?2·10^9,?L?≤?R).

Output

Print the desired number of integers x.

Sample Input

0 3 3 5 21 
   
4 3 0 6 17

Sample Output

   3 
   
 2

Hint

Problem Idea

解题思路:

【题意】
已知a1,b1,a2,b2,问区间[L,R]内有多少个数x满足x?=?a1k'?+?b1?=?a2l'?+?b2(k',?l'?≥?0)

【类型】
中国剩余定理

【分析】

对于式子

显然可以转化为

一元模线性方程组?

那还客气什么,套个中国剩余定理的模板

当然,这还没完,不然怎么会有那么多人错呢

利用中国剩余定理,我们求出了b和n,那么一元模线性方程组的解为b,b+n,b+2n,b+3n,……

接下来,我们要确定的是,这么多解落在区间[L,R]内的有多少个

所以区间大小可以进行缩小,L=max{L,b1,b2},此时如果L>R,显然无解

接着要求解b+kn落在区间[L,R]内时,k的取值范围

剩下的就是向上取整、向下取整等各种处理,注意细节就行,过程中可能会超int大小范围

【时间复杂度&&优化】
尴尬,这个时间复杂度不会算

题目链接→Codeforces Problem 710D Two Arithmetic Progressions

Source Code

/*Sherlock and Watson and Adler*/
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<bitset>
#include<cmath>
#include<complex>
#include<string>
#include<algorithm>
#include<iostream>
#define eps 1e-9
#define LL long long
#define PI acos(-1.0)
#define bitnum(a) __builtin_popcount(a)
using namespace std;
const int N = 2;
const int M = 100005;
const int inf = 1000000007;
const int mod = 1000000007;
int group;
LL n[N],a[N];
LL Egcd(LL a,LL b,LL &x,LL &y)
{if(b==0){x=1,y=0;return a;}LL d,tp;d=Egcd(b,a%b,x,y);tp=x;x=y;y=tp-a/b*y;return d;
}
pair<LL,LL> solve()
{int i;bool flag = false;LL n1 = n[0], n2, b1 = a[0], b2, bb, d, t, k, x, y;for (i = 1; i < group; i++){n2 = n[i], b2 = a[i];bb = b2 - b1;d = Egcd (n1, n2, x, y);if (bb % d)     //模线性解k1时发现无解{flag = true;break;}k = bb / d * x;    //相当于求上面所说的k1【模线性方程】t = n2 / d;if (t < 0) t = -t;k = (k % t + t) % t;    //相当于求上面的K`b1 = b1 + n1*k;n1 = n1 / d * n2;}if(flag)return make_pair(-1,-1);     //无解
/******************求正整数解******************/if(b1==0)    //如果解为0，而题目要正整数解，显然不行b1=n1;    //n1刚好为所有ni的最小公倍数，就是解了
/******************求正整数解******************/return make_pair(b1,n1);    //形成的解：b1, b1+n1, b1+2n1,..., b1+xni...
}
int main()
{int a1,b1,a2,b2;__int64 L,R;pair<LL,LL> ans;scanf("%d%d%d%d%I64d%I64d",&a1,&b1,&a2,&b2,&L,&R);group=2;//X mod n[i] = a[i] ,n[i]两两之间不一定互质做法n[0]=a1,a[0]=b1;n[1]=a2,a[1]=b2;L=max(L,max(a[0],a[1]));ans=solve();if(L>R){puts("0");return 0;}if(ans.second==0){if(ans.first>=L&&ans.first<=R)puts("1");elseputs("0");return 0;}if(ans.second<0){if(L>ans.first)L=(L-ans.first-1)/ans.second;elseL=(L-ans.first)/ans.second+1;if(R>=ans.first)R=(R-ans.first)/ans.second;elseR=(R-ans.first+ans.second+1)/ans.second;}else{if(L>ans.first)L=(L-ans.first-1)/ans.second;elseL=(L-ans.first)/ans.second-1;if(R>=ans.first)R=(R-ans.first)/ans.second;elseR=(R-ans.first-ans.second+1)/ans.second;}printf("%I64d\n",R>L?R-L:0);return 0;
}

菜鸟成长记

Codeforces Problem 710D Two Arithmetic Progressions(中国剩余定理)