Submission #65037759

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
using u128 = __int128_t;

template<typename T>
inline T readint() {
    T x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

template<typename T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

inline void writeln(ull x) {
    write(x);
    putchar('\n');
}

ull F(ull n, ull d) 
{
    if (!d)
        return (u128)(n - 1) * n * (2 * n - 1) / 6;
    ull t = n - d;
    u128 s1 = (u128)(t - 1) * t / 2;
    u128 s2 = (u128)(t - 1) * t * (2 * t - 1) / 6;
    u128 s3 = (u128)(d - 1) * d / 2;
    u128 s4 = (u128)(d - 1) * d * (2 * d - 1) / 6;
    u128 P1 = s2 + (u128)d * s1;
    u128 P2 = (u128)t * s3 + s4;
    return (ull)(P1 + P2);
}
int main()
{
    int T = readint<int>();
    while (T--)
    {
        ull N = readint<ull>(), M = readint<ull>(), A = readint<ull>(), 
            B1 = readint<ull>(), B2 = readint<ull>();
        if (!A)
        {
            writeln((u128)N * B1 * B2);
            continue;
        }
        ull g = std::gcd(A, M), L = M / g;
        ull b1 = B1 / g, c1 = B1 % g;
        ull b2 = B2 / g, c2 = B2 % g;
        ull d = (b2 + L - b1) % L;
        ull Sd = F(L, d);
        u128 sumL = (u128)g * g * Sd;
        sumL += (u128)g * (c1 + c2) * L * (L - 1) / 2;
        sumL += (u128)c1 * c2 * L;
        ull q = N / L, r = N % L;
        u128 ans = (u128)q * sumL;
        ull x = B1 % M, y = B2 % M;
        for (ull i = 0; i < r; i++)
        {
            ans += (u128)x * y;
            x += A;
            if (x >= M)
                x -= M;
            y += A;
            if (y >= M)
                y -= M;
        }
        writeln((ull)ans);
    }
    return 0;
}

Submission Info

Judge Result