Fun with Integers_牛客博客

https://codeforces.com/contest/1062/problem/D

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given a positive integer n greater or equal to 2. For every pair of integers a and b (2≤|a|,|b|≤n), you can transform a into b if and only if there exists an integer x such that 1<|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 0. 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 (2≤n≤100000) — 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 0.

Examples

input

output

input

output

input

output

Note

In the first example, the transformations are 2→4→(−2)→(−4)→22→4→(−2)→(−4)→2.

In the third example, it is impossible to perform even a single transformation.

C++版本一

题解：

从2到n，对于每个i属于[2,n]，对于每个可以整除i的x，把x和i/x加到dp【i】上，对于dp【i】在加上dp【i-1】完成递推

For every integer x(1≤x≤n), let's call D the set of integers that are able to be transformed into x. As you can see, if a could be transformed into b then −a could also be transformed into bb. Therefore |D| is always even. Let's build a graph consists of 2n−2nodes, numbered −n through n (except for −1, 0, and 1). There is an weighted undirected edge between node u and v if and only if u can be transformed into v. The weight of the edge is the score of the transformation. Every node in the graph has an even degree so you can split the graph into some connected components so that each components is an Euler circuit (a circuit that contains all the edges). Therefore you just need to find all those Euler circuits and maximize your score. Moreover, you can see that, if an integer a can be transformed into b then x and 2 are in the same component. Proof: Suppose a<b, there exists an integer x=b/a. If x=2 then it is proved, otherwise there exists an integer c=2x<b≤n. c and 2 are in the same component so x and 2 are also in the same component. Therefore, if we ignore all the nodes that have no edges attached to it, the graph will be connected. So you need to simply get the sum of all the weights of the edges.

The complexity is O(n+nlog(n)) since the number of edges can go up to nlog(n).

#include <iostream>
#include <stdio.h>
#include <math.h>
using namespace std;
typedef long long ll;
const int N=100000+100;
int n;
ll dp[N];
bool prime(int x){
    if(n==1)    return 0;
    if(n==2)    return 1;
    for(int i=2;i<=(int)sqrt(x);i++)
        if(x%i==0) return 0;
    return 1;

}
ll sloved(int x){
    ll ans=0;
    ll xend=x/2;
    for(int i=2;i<=(int)sqrt(x);i++){
        if(x%i==0){
            ans+=(x/i);
            if(x/i!=i)
                ans+=i;
        }
    }
    return ans;
}
int main()
{
    scanf("%d",&n);
    for(int i=2;i<=n;i++){
        if(prime(i))
            dp[i]=dp[i-1];
        else{
            dp[i]=dp[i-1]+sloved(i);
        }
        //cout << dp[i]*4 << endl;
    }
    cout << dp[n]*4 << endl;
    //cout << "Hello world!" << endl;
    return 0;
}

C++版本二

见过最简单的D题，直接在范围内找出倍数并保存倍数
自己看样例也就知道只是正负换了
因为会重复所不乘以4而是乘以2，看代码就知道了

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll a[1000005];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll n;
    while(cin>>n){
        memset(a,0,sizeof(a));
        for(ll i=2;i*2<=n;i++)
        for(ll j=2;j*i<=n;j++)
        a[i*j]+=i+j;
        ll ans=0;
        for(ll i=4;i<=n;i++)
        ans+=2*a[i];
        cout<<ans<<endl;
    }
    return 0;
}

C++版本三

考虑每个乘数x的贡献

x=2时 (+-2,+-4) (+-3,+-6) (+-4,+-8)...

x=3时 (+-2,+-6) (+-3,+-9) (+-4,+-12)...

......

规律就很显然了

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
 
int main()
{
    ll ans,n,i;
    scanf("%lld",&n);
    ans=0;
    for(i=2;i<=n;i++){
        ans+=(4ll*(n/i-1))*i;
    }
    printf("%lld\n",ans);
    return 0;
}