Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- using ll = long long;
- int const nax = 1e5 + 10;
- ll sum, f[nax];
- ll calc(int x, int n){
- n -= x - 1;
- int s = n / x;
- int res = n - x * s;
- ll toReturn = 0;
- toReturn += 1LL * x * s * (s + 1); /// (1 + ... + s) * x
- toReturn >>= 1;
- n += x - 1;
- return toReturn + 1LL * res * (s + 1);
- }
- int n;
- int main(){
- scanf("%d", &n);
- for(int a = n ; a >= 1 ; a -- ){
- ll toMinus = 0;
- ll toAdd = 0;
- for(int b = a ; b <= n ; b += a){
- toMinus += f[b];
- /// b = k * a
- /// a * k , a * (k + 1) , ... , a * sth
- /// divide by a * k
- /// -> [k / k] -> sth / k
- int sth = n / a;
- int k = b / a;
- toAdd += calc(k, sth);
- }
- toAdd -= toMinus;
- f[a] = toAdd;
- }
- printf("%lld\n", f[1]);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement