ICPC Central Europe Regional Contest 2019E. Zeldain Garden（除法分块，反函数求积分）

admin管理员组

文章数量:1573040

Boris is the chief executive officer of Rock Anywhere Transport (RAT) company which specializes in supporting music industry. In particular, they provide discount transport for manypopular rock bands. This time Boris has to move a large collection of quality Mexican concertloudspeakers from the port on the North Sea to the far inland capital. As the collection isexpected to be big, Boris has to organize a number of lorries to assure smooth transport. Themultitude of lorries carrying the cargo through the country is called a convoy

Boris wants to transport the whole collection in one go by a single convoy and without leavingeven a single loudspeaker behind. Strict E.U. regulations demand that in the case of largetransport of audio technology, all lorries in the convoy must carry exactly the same number ofpieces of the equipment.

To meet all the regulations, Boris would like to do some planning in advance, despite the fact thathe does not yet know the exact number of loudspeakers, which has a very significant influenceon the choices of the number and the size of the lorries in the convoy. To examine variousscenarios, for each possible collection size, Boris calculates the so-called “variability”, which isthe number of different convoys that may be created for that collection size without violatingthe regulations. Two convoys are different if they consist of a different number of lorries.

For instance, the variability of the collection of 6 loudspeakers is 4, because they may be evenlydivided into 1, 2, 3, or 6 lorries.

Input Specification

The input contains one text line with two integers N, M (1 \leq N \leq M \leq 10^{12})N,M(1≤N≤M≤10
12
), the minimumand the maximum number of loudspeakers in the collection.

Output Specification

Print a single integer, the sum of variabilities of all possible collection sizes betweenNN and MM,inclusive.

样例输入1复制
2 5
样例输出1复制
9
样例输入2复制
12 12
样例输出2复制
6
样例输入3复制
555 666
样例输出3复制
852

题意；
求所有n~m间每个数的约数数目和。

思路：
求前 n n n个数的约数数目和，就是求 ∑ ( n / i ) ∑(n/i) ∑(n/i)
这个过程可以用除法分块加速（对于所有 n/i 值相同的部分进行分块）。

貌似还看到了一种玄学的解法，反函数 f ( x ) = n / x f(x) = n/x f(x)=n/x面积求和来求解。
这个函数按照 ( x , x ) \sqrt{x},\sqrt{x}) x ​,x ​)对称，所以结果为sqrt(x)前的所有∑n/i乘以2，再减去sqrt(x) * sqrt(x)，这个过程可以画图看出来。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

typedef long long ll;

ll solve(ll n) {
    ll ans = 0;
    for(ll i = 1,j = 1;i <= n;) {
        j = n / (n / i);
        ans += (j - i + 1) * (n / i);
        i = j + 1;
    }
    return ans;
}

ll solve2(ll n) {
    ll ans = 0;
    ll t = sqrt(n);
    for(ll i = 1;i <= t;i++) {
        ans += n / i;
    }
    return ans * 2 - t * t;
}

int main() {
    ll n,m;scanf("%lld%lld",&m,&n);
    printf("%lld\n",solve2(n) - solve2(m - 1));
    return 0;
}

本文标签： 反函数除法积分europeRegional