数论分块

整数分块

求$\sum_{i=1}^{n}\left\lfloor\frac{n}{i}\right\rfloor$

性质1:分块的块数

$<=2\left\lfloor\sqrt{n}\right\rfloor$

当$i<=\left\lfloor{\sqrt{n}}\right\rfloor$时，$\lfloor\frac{n}{l}\rfloor$有$\lfloor{\sqrt{n}}\rfloor$种取法

当$i>\lfloor\sqrt{n}\rfloor$时，$\lfloor\sqrt{\frac{n}{i}}\rfloor<=\lfloor\sqrt{n}\rfloor$，最多也是$\sqrt{n}种$取法

性质2:l所在块的右端点为

$\left\lfloor{\frac{n}{\left\lfloor{\frac{n}{l}}\right\rfloor}}\right\rfloor$

[CQOI2007] 余数求和

题目描述

https://www.luogu.com.cn/problem/P2261

给出正整数 $n$ 和 $k$，请计算

$G(n, k) = \sum_{i = 1}^n k \bmod i$

其中 $k\bmod i$ 表示 $k$ 除以 $i$ 的余数。

输入格式

输入只有一行两个整数，分别表示 $n$ 和 $k$。

输出格式

输出一行一个整数表示答案。

样例输入 #1

10 5

样例输出 #1

29

样例 1 解释

$G(10, 5)=0+1+2+1+0+5+5+5+5+5=29$。

数据规模与约定

• 对于 $30\%$ 的数据，保证 $n , k \leq 10^3$。
• 对于 $60\%$ 的数据，保证 $n, k \leq 10^6$。
• 对于 $100\%$ 的数据，保证 $1 \leq n, k \leq 10^9$。

代码

#include <bits/stdc++.h>

using namespace std;
#define int long  long

signed main() {
#ifndef ONLINE_JUDGE
    freopen("../test.in", "r", stdin);
    freopen("../test.out", "w", stdout);
#endif
    int n, k;
    cin >> n >> k;
    int res = n * k;
    int r;
    for (int l = 1; l <= n; l = r + 1) {
        if (k / l == 0) break;
        r = min(k / (k / l), n);
        res -= (k / l) * (r - l + 1) * (l + r) / 2;
    }
    cout << res;
    return 0;
}

Strange Function

https://www.luogu.com.cn/problem/CF1542C

题面翻译

记 $f(i)$ 为最小的正整数数 $x$ 满足 $x$ 不是 $i$ 的因子。

现给出正整数 $n$，请计算出 $\sum_{i=1}^n f(i)$ 模 $10^9+7$ 的值。上述式子等价于 $f(1)+f(2)+\cdots+f(n)$。

本题含多组数据。令数据组数为 $t$，那么有 $1 \leq t \leq 10^4$，$1 \leq n \leq 10^{16}$

题目描述

Let $f(i)$ denote the minimum positive integer $x$ such that $x$ is not a divisor of $i$ .

Compute $\sum_{i=1}^n f(i)$ modulo $10^9+7$ . In other words, compute $f(1)+f(2)+\dots+f(n)$ modulo $10^9+7$ .

输入格式

The first line contains a single integer $t$ ( $1\leq t\leq 10^4$ ), the number of test cases. Then $t$ cases follow.

The only line of each test case contains a single integer $n$ ( $1\leq n\leq 10^{16}$ ).

输出格式

For each test case, output a single integer $ans$ , where $ans=\sum_{i=1}^n f(i)$ modulo $10^9+7$ .

样例输入 #1

6
1
2
3
4
10
10000000000000000

样例输出 #1

2
5
7
10
26
366580019

提示

In the fourth test case $n=4$ , so $ans=f(1)+f(2)+f(3)+f(4)$ .

• $1$ is a divisor of $1$ but $2$ isn't, so $2$ is the minimum positive integer that isn't a divisor of $1$ . Thus, $f(1)=2$ .
• $1$ and $2$ are divisors of $2$ but $3$ isn't, so $3$ is the minimum positive integer that isn't a divisor of $2$ . Thus, $f(2)=3$ .
• $1$ is a divisor of $3$ but $2$ isn't, so $2$ is the minimum positive integer that isn't a divisor of $3$ . Thus, $f(3)=2$ .
• $1$ and $2$ are divisors of $4$ but $3$ isn't, so $3$ is the minimum positive integer that isn't a divisor of $4$ . Thus, $f(4)=3$ .

Therefore, $ans=f(1)+f(2)+f(3)+f(4)=2+3+2+3=10$ .

思路

因为$f[i]=x$,即$x$是最小的不可以被$i$整除的数，那么$1,2,3...x-1$一定都是可以被$i$整除的

因此$i可以整除lcm(1,2,3...x-1)$，并且$i不可以整除lcm(1,2,3....x-1,x).$

因为$f[i]=x$,这里的$x$不会很大，估计不超过80，可以打表算一下$x=lcm(1,2,3..)$

所以我们可以考虑使用数论分块的思想，根据$x$的值，算有多少个数，满足$f[i]=x$.,假设有$num$个，那么对答案的贡献就是$num*x$

如何算有多少个呢？等于满足条件的数-不满足条件的数

$num=\frac{n}{lcm(1,2,3...x-1)}-\frac{n}{lcm(1,2,3...x)}$

设$t=lcm(1,2,3...x-1)$

则$num=\frac{n}{t}-\frac{n}{lcm(t,i)}$

代码

#include <bits/stdc++.h>

#define int long long
#define yes cout << "YES" << endl;
#define no cout << "NO" << endl;
#define IOS cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);
#define cxk 1
#define debug(s, x) if (cxk) cout << "#debug:(" << s << ")=" << x << endl;
using namespace std;

const int mod = 1e9 + 7;

void solve() {
    int n;
    cin >> n;
    int res = 0;
    int cur = 1;
    for (int i = 2;; i++) {
        int t = i * (n / cur - n / lcm(cur, i));
        t %= mod;
        res = (res + t) % mod;
        cur = lcm(cur, i);
        if (cur > n) break;
    }
    cout << res << endl;
}

signed main() {
    IOS
#ifndef ONLINE_JUDGE
    freopen("../test.in", "r", stdin);
    freopen("../test.out", "w", stdout);
#endif
    int _ = 1;
    cin >> _;
    while (_--) solve();
    return 0;
}