题解 | 余数求和

C++ 找到余数相同的部分

#include <iostream>
using namespace std;

int main() {
    long long a, b;
    cin >> a >> b;
    long long s = a*b;
    // for (int i=1; i<=a; i++) {   // 会超时
    // sum k%i = n*k - sum i*(k/i)
    long long r = 1;
    for (long long i=1; i<=min(a,b); i=r+1) {
        long long q = b/i;
        r = min(b/q, a);
        s -= q*(r+i)*(r-i+1)/2;
    }
    cout << s;
}
// 64 位输出请用 printf("%lld")

BISHI41 【模板】整除分块

#include <iostream>
using namespace std;

int main() {
    long long n;
    cin >> n;
    // 不是 n*(1+1/2+1/3+……+1/n) 而是 n/i 向下取整
    long long s = n;
    // for (long long i=2; i<=n; i++) { // 会超时
    long long r = 1;
    for (long long i=2; i<=n; i=r+1) {
        long long q = n/i;
        r = n/q; // r个余数为q
        // cout << q << ' ' << r << endl;
        s += (long long)(r-i+1)*q;
    }
    cout << s;
}
// 64 位输出请用 printf("%lld")