1257: [CQOI2007]余数之和

题目链接

bzoj1257: [CQOI2007]余数之和

题解

数论分块，乘等差数列求和

代码

#include<bits/stdc++.h> 
using namespace std; 
inline int read() { 
    int x = 0,f = 1; 
    char c = getchar(); 
    while(c < '0' || c > '9')c = getchar(); 
    while(c <= '9' && c >= '0')x = x * 10 + c - '0',c = getchar(); 
    return x * f; 
} 
long long n ,k ; 
int main() { 
    n = read(),k = read(); 
    long long ans = n * k; 
    for(long long l = 1,r;l <= n;l = r + 1 ) { 
            if(k / l) r = min(n,k / (k / l)); 
            else r =  n; 
            ans -=  (r - l + 1) * (k / l) * (l + r) >> 1; 
    } 
    printf("%lld
",ans); 
    return 0; 
}