Submission #19722879

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;
#define ll int64_
const int mod = 998244353, inv2 = (mod + 1) >> 1, inv6 = 166374059;

int inc(int x, int y) { return (x + y >= mod) ? (x + y - mod) : (x + y); }
int del(int x, int y) { return (x - y < 0) ? (x - y + mod) : (x - y); }

namespace EuclidLike
{
    struct Eans
    {
        int f, g, h;
    };
    Eans calc(int a, int b, int c, int n)
    {
        int s0 = n + 1;
        int s1 = 1ll * n * (n + 1) % mod * inv2 % mod;
        int s2 = 1ll * n * (n + 1) % mod * (2 * n + 1) % mod * inv6 % mod;
        if (!a)
        {
            int bz = b / c;
            int _f = 1ll * bz * s0 % mod;
            int _g = 1ll * bz * s1 % mod;
            int _h = 1ll * bz * bz % mod * s0 % mod;
            return {_f, _g, _h};
        }
        else if (a >= c || b >= c)
        {
            Eans tmp = calc(a % c, b % c, c, n);
            int bz = b / c, az = a / c;
            tmp.f = inc(tmp.f, inc(1ll * s1 * az, 1ll * s0 * bz % mod));
            tmp.g = inc(tmp.h, inc(1ll * az * s2 % mod, 1ll * bz * s1 % mod));
            tmp.h = inc(tmp.g, inc(inc(2ll * az * tmp.h % mod, 2ll * bz * tmp.f % mod), inc(inc(1ll * az * az % mod * s2 % mod, 2ll * az * bz % mod * s1 % mod), 1ll * bz * bz % mod * s0 % mod)));
            return tmp;
        }
        else
        {
            int m = (1ll * a * n + b) / c;
            Eans tmp = calc(c, c - b - 1, a, m - 1);
            int _f = del(1ll * n * m % mod, tmp.f);
            int _g = 1ll * del(del(1ll * n * (n + 1) % mod, tmp.f), tmp.h) * inv2 * mod;
            int _h = 1ll * del(1ll*n * m % mod * (m + 1) % mod, inc(inc(2ll * tmp.g % mod, 2ll * tmp.f % mod), _f));
            return {_f, _g, _h};
        }
    }
} // namespace EuclidLike

void solve()
{
    int A, B,C,D, n;
    cin >> A >> B >> C >>D;
     n = (D-2)/(C-B);
     
        
    auto z1=EuclidLike::calc(C, A, D,n).f-A/D;
    auto z2=EuclidLike::calc(B, A-1, D,n).f-(A-1)/D;
    int ans = n - (z1 - z2);
    
    cout << ans << endl;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T ;
    cin >> T;
    while (T--)
    {
        solve();
    }
}

Submission Info

Judge Result