Codeforces1062D. Fun with Integers(埃氏筛)

题目链接:传送门

题目:

D. Fun with Integers
time limit per test
seconds
memory limit per test
megabytes
input
standard input
output
standard output You are given a positive integer n
greater or equal to . For every pair of integers a and b (≤|a|,|b|≤n), you can transform a into b if and only if there exists an integer x such that <|x| and (a⋅x=b or b⋅x=a), where |x| denotes the absolute value of x . After such a transformation, your score increases by |x|
points and you are not allowed to transform a into b nor b into a anymore. Initially, you have a score of . You can start at any integer and transform it as many times as you like. What is the maximum score you can achieve?
Input A single line contains a single integer n
(≤n≤ ) — the given integer described above.
Output Print an only integer — the maximum score that can be achieved with the transformations. If it is not possible to perform even a single transformation for all possible starting integers, print .
Examples
Input
Copy Output
Copy Input
Copy Output
Copy Input
Copy Output
Copy Note In the first example, the transformations are →→(−)→(−)→ . In the third example, it is impossible to perform even a single transformation.

思路:

  如果一对数a,b可以通过x转换得到分数,那么a→b→-a→-b→a总共可以得到4*|x|的分数。

  不妨只考虑0 < a < b,0 < x的情况,把结果乘上4就好了。

  此时只能有a*x = b,即b为a的整数倍。对于给定的a,x可以取[2, n/a]范围内的所有值,为一个等差数列。用求和公式计算即可。

代码:

#include <bits/stdc++.h>

using namespace std;
typedef long long ll; int main()
{
ll n;
cin >> n;
ll ans = ;
for (ll i = ; i <= n/; i++) {
ll cnt = n/i;
ans += *(+cnt)*(cnt-)/;
}
cout << ans << endl;
return ;
}
上一篇:递归分治算法之二维数组二分查找(Java版本)


下一篇:TurboCAD Pro for Mac(二维绘图和三维建模工具)破解版安装