http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1008&cid=832

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

Problem Description

In the world line 1.048596%

今天的理科实验室依旧回响着气泡的大合唱。

梓川咲太一边看应考的题目一边听着声音的变化，同时思索该如何回答考察数学思维的题目......

就算解决了牧之原翔子和樱岛麻衣的问题，也终究要面对现实的考验。

“梓川你不是要和樱岛麻衣前辈考同一个大学吗？”

双叶理央坐在咲太的面前，今天也依然披着白大褂，正在准备不知名的实验。

“是啊。之前不是说过吗？所以我现在忙于备考。”

“我就友善的提醒你一句...”

“什么？”

“你看的是我的算法竞赛书......”双叶理央用略带担忧的声音这么说着。

梓川咲太突然回过神来，他翻了翻书本后面的内容，的确是和程序有关。但是前面的例题部分做的却和普通的参考书别无二致。

双叶拿回了她的算法书，找着梓川刚刚在看的部分。

“给出一个大于等于2的正整数n，对于一对数a和b(2<=|a|,|b|<=n,a!=b)，如果存在一个整数x(|x|>=1)使得ax=b（或bx=a)，就可以将a转换成b（或将b转换为a），转换后，你可以获得|x|的积分。”

一边说着，双叶就开始在黑板上写一些算式。

“不过，限制条件是，转换完毕后，就不能再使用由a转换成b或b转换成a的转换方式了。“

”一开始拥有的积分是0，现在给一个大于等于2的正数n，可以在2~n都取一次起点进行转换（更换起点时，转换方式不初始化）。请问最多可以获得多少分？”

“双叶老师，我实在是听不懂。”

梓川咲太很爽快的袒露了事实。

“

比如说n等于4的时候答案是11，因为

取起点为2时，你的最多得分是9。其中的一种得分方式是 2→(-2)→4→2→(-4)→(-2);

取起点为3时，你只能得1分，3→(-3);

取起点为4时，你别的转换方式都使用过，因此只能得1分，4→(-4)。

所以最终答案是9+1+1=11,明白了吗？

”

黑板上已经密密麻麻写了一堆公式，在右下角又写了一个Accepted。看来双叶理央已经在脑内解决了这个问题。

不过对于咲太来说这依旧是一个难题。虽然不是应考的范围，但既然看了这么久，也就顺便解答出来吧。

 

 

Input

多组输入输出。

对于每一组数据，输入一个整数n(2<=n<=100000)

保证n的个数小于200,n的总和不超过5000000

 

 

Output

对于每一组样例

输出梓川咲太最大能够得到的分数

 

 

Sample Input


 

2

4

6

 

 

Sample Output


 

1

11

33

C++版本一

预处理一下

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG

using namespace std;
typedef long long ll;
const int N=100000+10;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m;
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;
    for(int i=2;i<=(int)sqrt(x);i++){
        if(x%i==0){
            ans+=i;
            if(x/i!=i)
                ans+=(x/i);
        }
    }
    return ans;
}
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    for(int i=2;i<=N;i++){
        if(prime(i))
            dp[i]=dp[i-1];
        else{
            dp[i]=dp[i-1]+sloved(i);
        }
    }
    while(~scanf("%d",&n)){
    cout <<dp[n]*4+n-1 << endl;
    }
    //cout << "Hello world!" << endl;
    return 0;
}

C++版本二

https://www.cnblogs.com/MingSD/p/10050324.html

题解：我们可以从样例分析中发现，我们可以经过4次跳跃之后返回到原来的这个地方。

也就是说，我们每次走到一个新的位置之后，我们可以遍历他的所有因子，再返回到这个位置，然后继续按原来的路径行事。

我们不用管他怎么走，只需要明白每出现一个数会对答案产生什么影响就好了。

最后 是 x -> -x 。

 

#include<bits/stdc++.h>
using namespace std;
#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);
#define LL long long
#define ULL unsigned LL
#define fi first
#define se second
#define pb push_back
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define lch(x) tr[x].son[0]
#define rch(x) tr[x].son[1]
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
typedef pair<int,int> pll;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const LL mod =  (int)1e9+7;
const int N = 1e5 + 100;
int vis[N];
void init(){
    for(int i = 2; i < N; ++i){
        for(int j = i+i, t = 2; j < N; j+=i, t++){
                vis[j] += t;
        }
    }
}
int main(){
    init();
    int n;
    while(~scanf("%d", &n)){
        LL sum = 0;
        for(int i = 2; i <= n; ++i){
            sum += vis[i];
        }
        printf("%lld\n", sum*4+n-1);
    }
    return 0;
}