Zhiwei Zhang included in Algorithm

2020-10-07 2020-10-07 233 words 2 minutes

Contents

Description

给出整数$n,k$,计算$G(n,k)=\sum\limits_{i=1}^n=k \ mod \ i$,$1<=n,k<=1e9$

Solution

将k mod i展开可以得到$k - i*\lfloor \frac{k}{i} \rfloor$ 将求和式子展开可以得到$ \sum\limits_{i=1}^n = nk-\sum\limits_{i=1}^n i * \lfloor\frac{k}{i} \rfloor $ 利用整除分块，可以发现，对于相同的$\lfloor\frac{k}{i} \rfloor$，即每个区间$l 到 r$，每次只需要再对i求和即可即每次计算$(r-l+1)\lfloor \frac{k}{i} \rfloor * (l+r)/2$

Note

在分块的时候误写为r=N/(N/i)导致调试耽误大量时间，而且交了四发才发现

1
2
3
4
5
6
7


for (ll l = 1, r; l <= N; l = r + 1) {
        if (l > K) {
            break;
        }
        r = min(N, K/(K/l));
        ans -= (r - l + 1)*(K/l)*(l + r)/2;
    }

Code

 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


//https://www.luogu.com.cn/problem/P2261
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
#include <cmath>
#include <map>
#include <set>
#define mem(a,b) memset(a,b,sizeof(a))
#define debug cout<<0<<endl
#define ll long long
const int MAXN = 1e2 + 10;
const int MOD = 1e9 + 7;
using namespace std;

ll ans = 0;

void solve(ll N, ll K) {
    ans = N*K;
    for (ll l = 1, r; l <= N; l = r + 1) {
        if (l > K) {
            break;
        }
        r = min(N, K/(K/l));
        ans -= (r - l + 1)*(K/l)*(l + r)/2;
    }
    cout << ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll N, K; cin >> N >> K;
    solve(N, K);
    return 0;
}