admin管理员组文章数量:1573361
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
#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;
}
版权声明:本文标题:ICPC Central Europe Regional Contest 2019E. Zeldain Garden(除法分块,反函数求积分) 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/dongtai/1727725287a1127151.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论