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:
Love "A"
New Year and Permutation
Maximum flow - Push-relabel algorithm
Washer, Dryer, Folder
Image Preview
Breadth-first search
Cowboy Beblop at his computer
Chain Reaction
Landmarks
Party
Born This Way
A + B Strikes Back
Helga Hufflepuff's Cup
Orchestra
Calculating the determinant of a matrix by Gauss
Half-plane intersection - S&I Algorithm in O(Nlog N)
Two-gram
0-1 BFS
PE Lesson
Huffman Coding on Segment
Falling Blocks
Vanya and Cubes
The Brand New Function
Orac and Game of Life
Beautiful Sequence
Sereja and the Arrangement of Numbers
Field expansion
Parity Game
Om Nom and Spiders
Yui and Mahjong Set
Flows with demands
Suns and Rays