rt,数论推柿子做法,莫名WA了。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e9 + 10;
int l, r, a1, b1, a2, b2, ans, x, y, c, llim, rlim, ga2;
int exgcd(int a, int b) {
if(b == 0) {
x = 1, y = 0;
return a;
}
int ret = exgcd(b, a % b); int t = x;
x = y; y = t - (a / b) * y;
return ret;
}
int divu(int a, int b){ return a >= 0 ? (a + b - 1) / b : a / b; }
int divd(int a, int b) { return a >= 0 ? a / b : (a - b + 1) / b; }
signed main() {
scanf("%lld%lld%lld%lld%lld%lld", &a1, &b1, &a2, &b2, &l, &r);
b1 %= a1, b2 %= a2;
if(b2 < b1) swap(b1, b2), swap(a1, a2);
c = exgcd(a1, a2);
if(b2 == b1) {
c = a1 * a2 / c;
int ans = divd(r - b1, c) - divu(l - b1, c) + 1;
return printf("%lld\n", ans), 0;
}
ga2 = a2 / c;
if((b2 - b1) % c != 0) return puts("0"), 0;
c = (b2 - b1) / c * a1;
return 0;
llim = divu(l - b1, c), rlim = (r - b1) / c;
int ans = divd(rlim - x, ga2) - divu(llim - x, ga2) + 1;
printf("%lld\n", ans);
return 0;
}