Educational Codeforces Round 5 E. Sum of Remainders

問題

codeforces.com

解法

前似たような問題解いてましたね…
mayokoex.hatenablog.com
上の記事のは問題設定がわかりにくいですが, 今回のは問題設定が率直でわかりやすいです。

10^7 程度までは正直に余りを計算します。

それ以上の数での余りは, n/div の商が r になるものが O(sqrt(n)) しか考えられないことを利用します。ある数 div について, n/div = n/DIV を満たす最大の DIV を二分探索で求めます。すると, あまりの合計は,
(n-div*r) + (n-(div+1)*r) + ... + (n-DIV*r) = num*n - (div+DIV)*num/2 (num = DIV-div+1) です。

const ll MOD = 1e9+7;

// extgcd
ll extgcd(ll a, ll b, ll& x, ll& y) {
    ll d = a;
    if (b != 0) {
        d = extgcd(b, a % b, y, x);
        y -= (a / b) * x;
    } else {
        x = 1; y = 0;
    }
    return d;
}
// mod_inverse
ll mod_inverse(ll a, ll m) {
    ll x, y;
    extgcd(a, m, x, y);
    return (m+x%m) % m;
}

ll mul(ll x, ll y) {
    if (y==0) return 0;
    if (y==1) return x;
    if (y%2) return (x*mul(x, y-1))%MOD;
    ll tmp = mul(x, y/2);
    return (tmp*tmp)%MOD;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n, m;
    cin >> n >> m;
    ll ans = 0, maxi = 0, inv2 = mod_inverse(2, MOD);
    for (ll i = 1; i <= min(m, 10000000ll); i++) {
        maxi = i;
        (ans += n%i) %= MOD;
    }
    if (maxi < m) {
        ll div = maxi+1;
        while (div < m) {
            ll r = n/div;
            ll low = div, high = m+1;
            while (high-low > 1) {
                ll med = (high+low)/2;
                if (n/med == r) low = med;
                else high = med;
            }
            ll num = low-div+1;
            ll tmp = (n%MOD)*(num%MOD)%MOD;
            ll minus = (r%MOD)*((div+low)%MOD);
            minus %= MOD;
            (minus *= (num%MOD)) %= MOD;
            (minus *= inv2) %= MOD;
            tmp -= minus;
            (ans += tmp) %= MOD;
            div = low+1;
        }
    }
    ans = (ans+MOD)%MOD;
    cout << ans << endl;
    return 0;
}