首页 > 代码库 > [BZOJ 1257] [CQOI2007] 余数之和sum 【数学】
[BZOJ 1257] [CQOI2007] 余数之和sum 【数学】
题目链接：BZOJ - 1257
题目分析
首先， a % b = a - (a/b) * b，那么答案就是 sigma(k % i) = n * k - sigma(k / i) * i (1 <= i <= n)
前面的 n * k 很容易算，那么后面的 sigma(k / i) * i，怎么办呢？
我们可以分情况讨论，就有一个 O(sqrtk) 的做法。
1）当 i < sqrtk 时，直接枚举算这一部分。
2）当 i >= sqrtk 时， k / i <= sqrtk 。所以我们就可以枚举 k / i ，即枚举 [1, sqrtk] 的每一个数字。
那么，对于我们枚举的每一个数字 x ，以它为 k / i 的 i 一定是连续的一段，它们的和可以用等差数列求和公式算出。
于是就很明确了。
代码
#include <cstdio>#include <cstdlib>#include <cstring>#include <algorithm>#include <cmath>#include <iostream> using namespace std; int n, k, SQRTK, L, R; typedef long long LL; LL Ans; int main(){ scanf("%d%d", &n, &k); Ans = 0ll; if (n > k) Ans += (LL)(n - k) * k; n = n > k ? k : n; SQRTK = sqrt(k * 1.0); for (int i = 1; i <= SQRTK; i++) { if (i > n) break; Ans += (LL)k % i; } for (int i = 1; i <= SQRTK; i++) { L = (k / (i + 1)) + 1; L = L <= SQRTK ? SQRTK + 1: L; R = k / i; R = R > n ? n : R; if (R < L) continue; Ans += (LL)(R - L + 1) * ((k % L) + (k % R)) >> 1; } printf("%lld\n", Ans); return 0;}
[BZOJ 1257] [CQOI2007] 余数之和sum 【数学】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。