P2261 [CQOI2007] 余数求和

dzy15373891653 · 2025-02-10 15:27:48 · 题解

//这题数据范围大，采用整数分块,最多有根号n个块，不会超时。 
//因为 a % b == a * n - 求和 i * [k / i](下取整) 
#include <iostream>
#define int long long

using namespace std;

const int N = 1e9 + 5;

int n,k,r,ans;//记得开long long 

signed main(){

    cin >> n >> k;

    for (int l = 1;l <= n;l = r + 1){ //l,表示区间左端点，r,表示区间右端点,因为每次计算的是一个块的总长度，所以每次都要跳到右端点加1，跳到第二个块 

        if (k / l == 0) r = n;//如果说后面块的长度不够了，右端点就为n 
        else r = min (k / (k / l) , n);//否则的话，就让右端点在块长和n之间取个小的 

        ans += (r - l + 1) * (k / l) * (l + r) / 2;//(r - l + 1)为块长，(k / l)表示公式的变化，(l + r) / 2表示平均值 

    }
    cout << n * k - ans << '\n';//套公式 
    return 0;//华丽结束 
}