2019-team0x03/like_euclid

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
/*
ll f(ll a, ll b, ll c, ll n) {
    ll ret = 0;
    for(int i = 0; i <= n; ++i)
        ret += (a * i + b) / c;
    return ret;
}

ll g(ll a, ll b, ll c, ll d) {
    ll ret = 0;
    for(int i = 0; i <= n; ++i)
        ret += (a * i + b) / c * i;
    return ret;
}

ll h(ll a, ll b, ll c, ll d) {
    ll ret = 0;
    for(int i = 0; i <= n; ++i)
        ret += ((a * i + b) / c) * ((a * i + b) / c);
    return ret;
}
*/
ll f(ll a, ll b, ll c, ll n) {
    ll ret = (a / c) * n * (n + 1) / 2 + (b / c) * (n + 1);
    a %= c, b %= c;
    if(!a) return ret;
    ll m = (a * n + b) / c;
    return ret + n * m - f(c, c - b - 1, a, m - 1);
}

ll g(ll a, ll b, ll c, ll n) {
    ll ret = (a / c) * n * (n + 1) * (2 * n + 1) / 6 + (b / c) * n * (n + 1) / 2;
    a %= c, b %= c;
    if(!a) return ret;
    ll m = (a * n + b) / c;
    return ret + (m * n * (n + 1) / 2 - f(c, c - b - 1, a, m - 1) - h(c, c - b - 1, a, m - 1)) / 2;
}

ll h(ll a, ll b, ll c, ll n) {
    ll ret = (a / c) * (a / c) * n * (n + 1) * (2 * n + 1) / 6 + (b / c) * (b / c) * (n + 1) + (a / c) * (b / c) * n * (n + 1);
    a %= c, b %= c;
    if(!a) return ret;
    ll m = (a * n + b) / c;
    return ret + m * (m + 1) * n - 2 * g(c, c - b - 1, a, m - 1) - 2 * f(c, c - b - 1, a, m - 1) - f(a, b, c, n);
}
}}}

/*
ll f(ll a, ll b, ll c, ll n) {
    ll ret = 0;
    for(int i = 0; i <= n; ++i)
        ret += (a * i + b) / c;
    return ret;
}
ll g(ll a, ll b, ll c, ll d) {
    ll ret = 0;
    for(int i = 0; i <= n; ++i)
        ret += (a * i + b) / c * i;
    return ret;
}
ll h(ll a, ll b, ll c, ll d) {
    ll ret = 0;
    for(int i = 0; i <= n; ++i)
        ret += ((a * i + b) / c) * ((a * i + b) / c);
    return ret;
}
*/
ll f(ll a, ll b, ll c, ll n) {
    ll ret = (a / c) * n * (n + 1) / 2 + (b / c) * (n + 1);
    a %= c, b %= c;
    if(!a) return ret;
    ll m = (a * n + b) / c;
    return ret + n * m - f(c, c - b - 1, a, m - 1);
}
ll g(ll a, ll b, ll c, ll n) {
    ll ret = (a / c) * n * (n + 1) * (2 * n + 1) / 6 + (b / c) * n * (n + 1) / 2;
    a %= c, b %= c;
    if(!a) return ret;
    ll m = (a * n + b) / c;
    return ret + (m * n * (n + 1) / 2 - f(c, c - b - 1, a, m - 1) - h(c, c - b - 1, a, m - 1)) / 2;
}
ll h(ll a, ll b, ll c, ll n) {
    ll ret = (a / c) * (a / c) * n * (n + 1) * (2 * n + 1) / 6 + (b / c) * (b / c) * (n + 1) + (a / c) * (b / c) * n * (n + 1);
    a %= c, b %= c;
    if(!a) return ret;
    ll m = (a * n + b) / c;
    return ret + m * (m + 1) * n - 2 * g(c, c - b - 1, a, m - 1) - 2 * f(c, c - b - 1, a, m - 1) - f(a, b, c, n);
}