数论分块——学习

引子

现有一公式，求 $ans={\sum }_{i=1}^n\lfloor \frac{n}{i}\rfloor$ans=∑i=1n​⌊in​⌋
观察发现我们可以在O(n)的时间复杂度内解决该问题
继续观察，会发现 $\lfloor \frac{n}{i}\rfloor$⌊in​⌋在一段区间内是具有相同的值
令 $\lfloor \frac{n}{i}\rfloor =k$⌊in​⌋=k 则有
⌊⌊in​⌋n​⌋<=⌊in​⌋n​=j
故当前块最远位置为j， 块长为(j - i + 1)

题目分析

牛客-数论之神
对于 $\lfloor \frac{n}{1}\rfloor ,\lfloor \frac{n}{2}\rfloor ,\dots \dots ,\lfloor \frac{n}{n-1}\rfloor ,\lfloor \frac{n}{n}\rfloor$⌊1n​⌋,⌊2n​⌋,……,⌊n−1n​⌋,⌊nn​⌋
当 2 * k <= n < k * (k + 1) 共有2 * k - 1种不同的数
当 k * (k + 1) <= n < (k + 1) * (k + 1) 共有 2 * k 种不同的数
对结果升序
1, 2, ……, k, n / k, n / (k - 1), ……, n

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int main()
{
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while(t --)
    {
        ll n, p;
        cin >> n >> p;//第p大
        ll k = (ll)sqrt(n);
        ll sum = 2 * k;//k * k <= n < k * (k + 1) 有(2 * k -1)个不同值
        if(n < k * (k + 1))//k * (k + 1) <= n < (k + 1) * (k + 1) 有(2 * k)个不同值
            sum --;
        ll ans;
        if(p <= k)//降序
        {
            ans = n / p;
        }
        else
        {
            ans = sum - p + 1;//有连续的1～k
        }
        cout << sum << " " << ans << endl;
    }
}

bzoj-1968-约数研究
题目定义f(x) 为x的约数个数
先求 $ans={\sum }_{i=1}^{n}f\left(i\right)$ans=∑i=1n​f(i)
将式子转换一下其实就是 $ans={\sum }_{i=1}^n\lfloor \frac{n}{i}\rfloor$ans=∑i=1n​⌊in​⌋
简单分块即可

/*
题意是1到n的约数个数之和
可以转换成1到n的(n / i)向下取整
一维数论分块模板题
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int main()
{
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    ll ans = 0;
    for(int i = 1, j = 1; i <= n; i = j + 1)
    {
        j = n / (n / i);//当前块能到达的最远位置
        ans += 1l * (j - i + 1) * (n / i);//(n / i)为当前块的大小
    }
    cout << ans << endl;
}

bzoj 1257 余数之和
题目要求
$\begin{array}{c}{\displaystyle ans=\sum _{i=1}^n\left(kmod\hspace{0.17em}\hspace{0.17em}i\right)}\\ {\displaystyle ans=\sum _{i=1}^n(k-i\ast \lfloor \frac{k}{i}\rfloor )}\\ {\displaystyle ans=n\ast k-\sum _{i=1}^n(i\ast \lfloor \frac{k}{i}\rfloor )}\end{array}$ans=i=1∑n​(kmodi)ans=i=1∑n​(k−i∗⌊ik​⌋)ans=n∗k−i=1∑n​(i∗⌊ik​⌋)​
在一定区间 $\lfloor \frac{k}{i}\rfloor$⌊ik​⌋为定值，i成等差数列变化

/*
数论分块基础题1到n的floor(k / i) * i (floor为向下去整)
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int main()
{
    ios::sync_with_stdio(false);
    int n, k;
    cin >> n >> k;
    ll ans = 1ll * n * k;
    if(n >= k)
        n = k;
    for(int i = 1, j = 1; i <= n; i = j + 1)
    {
        j = k / (k / i);
        int d = k / i;
        if(j >= n)
            j = n;
        ans -= 1ll * (j - i + 1) * (j + i) * d / 2;//i呈等差数列
    }
    cout << ans << endl;
}

bzoj 2956 模积和
${\sum }_{i=1}^n{\sum }_{j=1}^m\left(nmod\hspace{0.17em}\hspace{0.17em}i\right)\ast \left(mmod\hspace{0.17em}\hspace{0.17em}j\right)$∑i=1n​∑j=1m​(nmodi)∗(mmodj) (i != j)
原式可变：
$\begin{array}{c}{\displaystyle \sum _{i=1}^n\sum _{j=1}^m\left(nmod\hspace{0.17em}\hspace{0.17em}i\right)\ast \left(mmod\hspace{0.17em}\hspace{0.17em}j\right)-\sum _{i=1}^{\min (n,m)}\left(nmod\hspace{0.17em}\hspace{0.17em}i\right)\ast \left(mmod\hspace{0.17em}\hspace{0.17em}i\right)}\\ {\displaystyle \sum _{i=1}^n\left(nmod\hspace{0.17em}\hspace{0.17em}i\right)\ast \sum _{j=1}^m\left(mmod\hspace{0.17em}\hspace{0.17em}j\right)-\sum _{i=1}^{\min (n,m)}\left(nmod\hspace{0.17em}\hspace{0.17em}i\right)\ast \left(mmod\hspace{0.17em}\hspace{0.17em}i\right)}\end{array}$i=1∑n​j=1∑m​(nmodi)∗(mmodj)−i=1∑min(n,m)​(nmodi)∗(mmodi)i=1∑n​(nmodi)∗j=1∑m​(mmodj)−i=1∑min(n,m)​(nmodi)∗(mmodi)​
后式可变：
$\begin{array}{c}{\displaystyle \sum _{i=1}^{\min (n,m)}\left(nmod\hspace{0.17em}\hspace{0.17em}i\right)\ast \left(mmod\hspace{0.17em}\hspace{0.17em}i\right)}\\ {\displaystyle \sum _{i=1}^{\min (n,m)}(n-i\ast \lfloor \frac{n}{i}\rfloor )\ast (m-i\ast \lfloor \frac{m}{i}\rfloor )}\\ {\displaystyle \sum _{i=1}^{\min (n,m)}(n\ast m-n\ast i\lfloor \frac{m}{i}\rfloor -m\ast i\lfloor \frac{n}{i}\rfloor +i^2\lfloor \frac{n}{i}\rfloor \lfloor \frac{m}{i}\rfloor )}\end{array}$i=1∑min(n,m)​(nmodi)∗(mmodi)i=1∑min(n,m)​(n−i∗⌊in​⌋)∗(m−i∗⌊im​⌋)i=1∑min(n,m)​(n∗m−n∗i⌊im​⌋−m∗i⌊in​⌋+i2⌊in​⌋⌊im​⌋)​

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 19940417;//mod不是质数
const ll inv = 3323403;//6在模mod意义下的逆元，6^(phi(mod) - 1)
ll sum(ll l, ll r) { return ((l + r) * (r - l + 1) / 2) % mod; }
ll sum_pow_two(ll n) { return n * (n + 1) % mod * (2 * n + 1) % mod * inv % mod; }//1^2 + 2^2 + …… + n^2 = n * (n + 1) * (2 * n + 1) / 6
ll cal(ll n)
{
    ll ans = n * n % mod;
    for(ll i = 1, j = 1; i <= n; i = j + 1)
    {
        j = n / (n / i);
        ans = (ans - (n / i) * sum(i, j) % mod + mod) % mod;
    } 
    return ans;
}
ll cal(ll n, ll m)
{
    if(n > m)
        swap(n, m);//让n为最小
    ll ans = n * n % mod * m % mod;
    for(ll i = 1, j = 1; i <= n; i = j + 1)
    {
        j = min(n / (n / i), m / (m / i));
        ll t1 = (n * (m / i) % mod + m * (n / i) % mod) % mod * sum(i, j) % mod;
        ll t2 = ((n / i) * (m / i) % mod * (sum_pow_two(1ll * j) - sum_pow_two(1ll * (i - 1)) + mod) % mod + mod) % mod;
        ans = ((ans - t1 + t2) % mod + mod) % mod;
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    ll n, m;
    cin >> n >> m;
    ll ans = ((cal(n) * cal(m) % mod - cal(n, m)) % mod + mod) % mod;
    cout << ans << endl;
}