You are given two arithmetic progressions: a 1 k + b 1 and a 2 l + b 2. Find the number of integers x such that L ≤ x ≤ R and x = a 1 k‘ + b 1 = a 2 l‘ + b 2, for some integers k‘, l‘ ≥ 0.
Input
The only line contains six integers a 1, b 1, a 2, b 2, L, R (0 < a 1, a 2 ≤ 2·109, - 2·109 ≤ b 1, b 2, 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
Solution:
#include <bits/stdc++.h> using namespace std; void solve(long long a, long long b, long long &x, long long &y) { if (b == 0) { x = 1; y = 0; return; } long long xx, yy; solve(b, a % b, xx, yy); // b * xx + (a - (a / b) * b) * yy == 1 // a * yy + b * (xx - yy * (a / b)) == 1 x = yy; y = xx - yy * (a / b); } long long gcd(long long a, long long b) { while (a > 0 && b > 0) { if (a > b) { a %= b; } else { b %= a; } } return a + b; } int main() { long long a1, b1, a2, b2, L, R; cin >> a1 >> b1 >> a2 >> b2 >> L >> R; // a1 * k + b1 == a2 * l + b2 // a1 * k - a2 * l == b2 - b1 long long g = gcd(a1, a2); if ((b2 - b1) % g != 0) { cout << 0 << endl; return 0; } long long k, l; solve(a1, a2, k, l); k *= (b2 - b1) / g; l *= (b1 - b2) / g; long long c1 = a1 / g; long long c2 = a2 / g; long long shift = min(k / c2, l / c1); k -= shift * c2; l -= shift * c1; while (k < 0 || l < 0) { k += c2; l += c1; } while (k >= c2 && l >= c1) { k -= c2; l -= c1; } long long start = a1 * k + b1; assert(start == a2 * l + b2); long long step = a1 / g * a2; if (start < L) { start += (L - start) / step * step; } while (start < L) { start += step; } long long ans = 0; if (start <= R) { ans = (R - start) / step + 1; } cout << ans << endl; return 0; }
Related posts:
Cow and Friend
New Year and Three Musketeers
Huffman Coding on Segment
Face Detection
Magic Grid
Generating all $K$-combinations
Captains Mode
Coffee Varieties (hard version)
Kirchhoff's theorem. Finding the number of spanning trees
Spyke Talks
Vertical decomposition
Wilbur and Points
Paint the Digits
Arbitrary-Precision Arithmetic
May Holidays
Long Beautiful Integer
Edge Weight Assignment
Race
K Paths
Random Function and Tree
Worms
Fish Weight
Bots
The Chocolate Spree
Booking System
Playing with Permutations
Montgomery Multiplication
Barcode
Slime and Biscuits
Not Same
The Door Problem
Bracket Sequence