题目背景
数学题, 无背景
题目描述
给出正整数 n 和 k, 计算 G(n, k)=k mod 1 + k mod 2 + k mod 3 + ... + k mod n 的值, 其中 k mod i 表示 k 除以 i 的余数. 例如 G(10, 5)=5 mod 1 + 5 mod 2 + 5 mod 3 + 5 mod 4 + 5 mod 5 ...... + 5 mod 10=0+1+2+1+0+5+5+5+5+5=29
输入输出格式
输入格式:
两个整数 n k
输出格式:
答案
推导一波:
- \[Ans = \sum_{i = 1}^{n}k \mod i\]
- \[=\sum_{i = 1}^{n}k - \lfloor \frac{k}{i}\rfloor * i\]
- \[= n * k - \sum_{i = 1}^{n}\lfloor\frac{k}{i}\rfloor * i\]
发现对于后面的 \(\lfloor\frac{k}{i}\rfloor\) 在一段区间内值不变, 故 \(sum\) 部分可以除法分块解决
对于每一块, 我们枚举左端点 \(L\) , 计算出右端点 \(R\) , 每次计算一块的总值,
右端点的计算方式 (打表得): 令 \(t = \lfloor \frac{k}{L} \rfloor\) , 分两种情况讨论:
\(t \not= 0\) , 则 \(r = \min (\lfloor \frac{k}{t} \rfloor , n)\)
\(t = 0\) , 则 \(R = n\) .
得到了一段区间的左右端点, 由 \(ans = \lfloor\frac{k}{i}\rfloor * i\) , 因为在此区间内 \(\lfloor\frac{k}{i}\rfloor\) 不变且为上面计算的 \(t\) , 我们由乘法分配律得到这一区间的答案为区间 \(i\) 平均值乘以 \(t\):\[(R - L + 1) / 2 * t\]
今后还可以用这个方法优化莫比乌斯反演, 在这里姑且先记住
- Code
- #include<iostream>
- #include<cstdio>
- #include<queue>
- #include<cstring>
- #include<algorithm>
- #define LL long long
- using namespace std;
- int RD(){
- int flag = 1, out = 0;char c = getchar();
- while(c <'0' || c> '9'){if(c == '-')flag = -1;c = getchar();}
- while(c>= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();}
- return flag * out;
- }
- int main(){
- LL n = RD(), k = RD();
- LL ans = k * n;
- int l, r;
- for(l = 1;l <= n;l = r + 1){
- LL t = k / l;
- if(t)r = min(n, k / t);
- else r = n;
- ans -= (r - l + 1) * t * (l + r) / 2;
- }
- printf("%lld\n", ans);
- return 0;
- }