Part 0 Preface

[Original title]（ https://www.luogu.com.cn/problem/AT_abc230_e )

Part 1 Description

*Given $$$N $$$.

*$ sum ^ N_ {i=1}\lfloor \frac{N}{i}\rfloor$。

Part 2 Analysis

When you see this question, it should not be difficult for you to think of direct violence for peace. After all, the question is very simple (at least it seems). The time complexity of such summation is $$$O (N) $$$. Although it is not very high in general, the data size of $N leq10 ^ {12} $determines that it is impossible to solve this method. The final result is TLE. (The code and evaluation results are given in Solve1).

Let's list the situation when $$$N=5 $$$.

$$$\lfloor\frac{5}{1}\rfloor=5,\lfloor\frac{5}{2}\rfloor=2,\lfloor\frac{5}{3}\rfloor=1,\lfloor\frac{5}{4}\rfloor=1,\lfloor\frac{5}{5}\rfloor=1$$$

It is not difficult to find that the last three results are $$$1 $$$. In other words, within a range of $$$l $$$to $$$r $$$, each $$$ lflour frac {N} {i} rflour $$$is a fixed value of $$$k $$$.

We can find all the different $$$ lflour frac {N} {i} rflour $$$, multiply them by their corresponding number, and add up to get the result.

In the interval, the right endpoint $$$r= lfcolor frac {N} {k} rfcolor $$$, and $$$k= lfcolor frac {N} {l} rfcolor $$$, so $$$r= lfcolor frac {N} { lfcolor frac {N} {l} rfcolor} rfcolor $$$.

So we just need to enumerate each $$$l, r $$$, calculate $$$k $$$, multiply by the number of interval elements $$$r-l+1 $$$, and add up. (The code and evaluation results are given in Solve2)

The essence of ontology is a problem of number theory partition, which can prove that the time complexity is $$$O ( sqrt {N}) $$$.

Part 3 code

• Solve1

#include <iostream>

#include <iomanip>

#include <cstdio>

#include <cstdlib>

#include <cmath>

using namespace std;

long long n,sum = 0;

int main()

{

scanf("%lld",&n);

for(long long i = 1;i<=n;i++)

{

sum+=(n/i);

}

printf("%lld",sum);

return 0;

}

• Solve2

#include <iostream>

#include <iomanip>

#include <cstdio>

#include <cstdlib>

#include <cmath>

using namespace std;

long long n,sum = 0;

int main()

{

scanf("%lld",&n);

for(long long l = 1,r;l<=n;l = r+1)

{

r = n/(n/l);

sum+=(r-l+1)*(n/l);

}

printf("%lld",sum);

return 0;

}

Part 4 Test information

! []( https://cdn.luogu.com.cn/upload/image_hosting/yl7sbkkh.png )

! []( https://cdn.luogu.com.cn/upload/image_hosting/vlqoj39c.png )

[Record (Solve1)]（ https://atcoder.jp/contests/abc230/submissions/39366695 )

[Record (Solve2)]（ https://atcoder.jp/contests/abc230/submissions/39366644 )