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:
Orchestra
Product transformation
Cách giải hay cho những bài toán trên vnspoj
Bulbo
Tanya and Password
Linova and Kingdom
New Year and Forgotten Tree
Fox And Jumping
Longest Saw
Ant colony
The Evil Temple and the Moving Rocks
Network Topology
Rectangle Puzzle
Captains Mode
Road Repair in Treeland
EKG
Pattern
Nearest Leaf
Paint the Digits
New Year Ratings Change
Three Problems
Buy Low Sell High
One-Based Arithmetic
Increase Sequence
Social Network
Packmen
Neural Network country
Remainders Game
International Olympiad
Bear and Contribution
Trips
Calculating the determinant of a matrix by Gauss