小G的约数_牛客博客

这是个比较简单的整除分块吧..

但是我不是数论选手，所以就先去写D了..

这个题还是比较裸的，如果知道约数和的写法的话

首先考虑直接求约数和不太现实，所以我们可以枚举约数，求约数对答案的贡献。

首先1~n所有的约数最大值不可能超过n

所以我们可以考虑所有的约数，用f(i)表示i的倍数在n之前有多少个，那么有公式:

$f(i) = \frac{n}{i}$

所以自然有下面的求和公式：

$f(n) = \sum{\lfloor\frac{n}{i} \rfloor *i}$

该和可以以 $O(sqrt(N))$ 的复杂度求和，所谓整除分块，具体证明不提(网上一搜一片)，如果你和我一样对于数学不敏感，那么就直接记住：

$\frac{N}{i} = \frac{N}{i'}时，i'的最大值是：\frac{N}{\frac{N}{i}}$

而且取值最多有 $2sqrt(N)$ 种，所以复杂度稳定在根号下

剩下的就套一下就好了，注意计算时涉及到等差数列求和：

/*** keep hungry and calm CoolGuang!  ***/
//#pragma GCC optimize(3)
#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define dl(x) printf("%lld\n",x);
#define di(x) printf("%d\n",x);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll INF= 1e18+7;
const ll maxn = 1e6+700;
const int M = 1e6+8;
const ll mod= 1e6+7;
const double eps = 1e-9;
const double PI = acos(-1);
template<typename T>inline void read(T &a){char c=getchar();T x=0,f=1;while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;}
ll n,m,p;
ll get(ll x){
    ll ans = 0;
    for(int i=1;i<=x;i++){
        int r = (x/(x/i));
        ans += (r-i+1ll)*(x/i)*(x+i)/2;
        i = r;
    }
    return ans;
}
int main(){
    read(n);
    printf("%lld\n",get(get(n)));
    return 0;
}