数论

题目大意 即求 $$ \sum_{i=a}^b \sum_{j=c}^d [\gcd(i,j) = k] $$ 分析 容易想到，独立出函数 $f(k)$ 使得 $$ f(k) = \sum_{i=1}^x \sum_{j=1}^y [\gcd(i,j) = k] $$ 利用 Mobius 反演化简，设 $F(d)$ $$ F(n) = \sum_{n \mid d} f(d) = \sum_{i=1}^x \sum_{j=1}^y [n \mid i][n \mid j] = \left\lfloor \frac{x}{n} \right\rfloor \left\lfloor \frac{y}{n} \right\rfloor $$ 反演化简有 $$ f(n) = \sum_{n \mid d} \mu\left(\frac{d}{n}\right)F(d) = \sum_{t=1}^{\min(x,y)} \mu(t) \left\lfloor \frac{x}{tn} \right\rfloor \left\lfloor \frac{y}{tn} \right\rfloor $$ 预处理出 $\mu(t)$ 的前缀和，剩下的就是一个二重分块了。...

题目大意 给出正整数 $n$ 和 $k$，请计算 $$ G(n, k) = \sum_{i = 1}^n k \bmod i $$ 分析 因为 $$ k \bmod i = k - i \left\lfloor \frac{k}{i} \right\rfloor $$ 因此有 $$ G(n,k) = nk - \sum_{i=1}^n i \left\lfloor \frac{k}{i} \right\rfloor $$ 后面需要整数分块。 int main() { ll n = rr(); ll k = rr(); ll sum = n * k; n = min(n, k); for (ll l = 1, r; l <= n; l = r + 1) { r = min(n, k / (k / l)); ll t = (l + r) * (r - l + 1) / 2; sum -= t * (k / l); } printf("%lld", sum); return 0; }