WA #3 mxqz
查看原帖
WA #3 mxqz
483928
Z1qqurat楼主2022/11/18 17:30

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;
}
2022/11/18 17:30
加载中...