Butteruni Blog
0%

数论做题记录（不定期更新）

发表于 更新于 分类于

[P2261 CQOI2007] 余数求和 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

求

公式推导如下 于是分块求解即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    ll n,k;
    cin >> n >> k;
    ll ans = n * k;
    for(ll l = 1,r = 0; l <= n;l = r + 1)
    {
        if(k / l != 0)
        {
            r = min(k / (k / l),n);
        }
        else 
        {
            r = n;
        }
        ans -= (k / l) * (r - l + 1) * (l + r) / 2;
    }
    cout << ans;
}

P3935 Calculating - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

计算 定义为 因数个数。

有公式

分块求解即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
ll clac(ll n)
{
    ll res = 0;
    for(ll l = 1,r;l <= n;l = r + 1)
    {
        r = n / (n / l);
        res = (res + ((r - l + 1) % mod) * ((n / l) % mod)) % mod;
    }
    return res;
}
int main()
{
    ll l,r,sum1 = 0,sum2 = 0;;
    cin >> l >> r;
    sum1 = clac(r);
    sum2 = clac(l - 1);
    cout << ((sum1 - sum2) % mod + mod) % mod; 
}

[P3455 POI2007] ZAP-Queries - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

求解 公式推导 预处理莫比乌斯函数后分块处理即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e18;
const int N = 5e4 + 10;
ll prime[N],sum[N],mul[N];
bool vis[N];
int cnt;
void init()
{
    vis[1] = 1;
    mul[1] = 1;
    for(int i = 2;i<=N;i++) 
    {
        if(!vis[i])//如果没有被筛过就是质数
        {
            prime[++cnt]=i;
            mul[i] = -1; 
        }
        for(int j = 1;j <= cnt;j++) 
        {
            if(1ll * i * prime[j] > N)
                break;
            vis[i * prime[j]] = 1;
            if(i % prime[j] == 0) 
            {
                mul[i * prime[j]] = 0;
                break;
            }
            mul[i * prime[j]] = -mul[i];
        }
    }
    for(int i = 1;i <= 50000;++i)
    {
        sum[i] = sum[i - 1] + mul[i];
    }
}
ll calc(ll n,ll m)
{
    ll res = 0;
    for(ll l = 1,r;l <= m;l = r + 1)
    {
        r = min(n / (n / l),m / (m / l));
        res += (sum[r] - sum[l - 1]) * (n / l) * (m / l);
    }
    return res;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    init();
    int t;
    cin >> t;
    while(t--)
    {
        ll a,b,d;
        cin >> a >> b >> d;
        a /= d,b /= d;
        if(a < b)
            swap(a,b);
        ll ans = calc(a,b);
        cout << ans << '\n';
    }
}

P1390 公约数的和 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

求 显然有 又 同样，预处理完后分块

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e6 + 10;
ll prime[N],sum[N],mul[N];
bool vis[N];
int cnt;
void init()
{
    vis[1] = 1;
    mul[1] = 1;
    for(int i = 2;i<=N;i++) 
    {
        if(!vis[i])//如果没有被筛过就是质数
        {
            prime[++cnt]=i;
            mul[i] = -1; 
        }
        for(int j = 1;j <= cnt;j++) 
        {
            if(1ll * i * prime[j] > N)
                break;
            vis[i * prime[j]] = 1;
            if(i % prime[j] == 0) 
            {
                mul[i * prime[j]] = 0;
                break;
            }
            mul[i * prime[j]] = -mul[i];
        }
    }
    for(int i = 1;i <= 2000000;++i)
    {
        sum[i] = sum[i - 1] + mul[i];
    }
}
ll calc(ll n)
{
    ll res = 0;
    for(ll l = 1,r;l <= n;l = r + 1)
    {
        r = n / (n / l);
        res += (sum[r] - sum[l - 1]) * (n / l) * (n / l);
    }
    return res;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    ll n;
    cin >> n;
    ll ans = 0;
    init();
    for(ll i = 1;i <= n;++i)
    {
        ans += calc(n / i) * i;
    }
    cout << (ans - (n + 1) * n / 2) / 2 << '\n';
}

[P3327 [SDOI2015] 约数个数和 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)](https://www.luogu.com.cn/problem/P3327)

求 定义为 因数个数

由公式 有 又 于是 分块即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e4 + 10;
ll prime[N],sum[N],mul[N];
bool vis[N];
ll pre[N];
int cnt;
void init()
{
    vis[1] = 1;
    mul[1] = 1;
    for(int i = 2;i<=N;i++) 
    {
        if(!vis[i])//如果没有被筛过就是质数
        {
            prime[++cnt]=i;
            mul[i] = -1; 
        }
        for(int j = 1;j <= cnt;j++) 
        {
            if(1ll * i * prime[j] > N)
                break;
            vis[i * prime[j]] = 1;
            if(i % prime[j] == 0) 
            {
                mul[i * prime[j]] = 0;
                break;
            }
            mul[i * prime[j]] = -mul[i];
        }
    }
    for(int i = 1;i <= 50000;++i)
    {
        sum[i] = sum[i - 1] + mul[i];
    }
    for(int i = 1;i <= 5e4;++i)
    {
        ll res = 0;
        for(ll l = 1,r;l <= i;l = r + 1)
        {
            r = i / (i / l);
            res += (r - l + 1) * (i / l);
        }
        pre[i] = res;
    }
}
ll calc(ll n,ll m)
{
    ll res = 0;
    for(ll l = 1,r;l <= n;l = r + 1)
    {
        r = min(n / (n / l),m / (m / l));
        res += (sum[r] - sum[l - 1]) * pre[n / l] * pre[m / l];
    }
    return res;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    init();
    int t;
    cin >> t;
    while(t--)
    {
        ll n,m;
        cin >> n >> m;
        if(n > m)
            swap(n,m);
        ll ans = calc(n,m);
        cout << ans << "\n";
    }
}