Advertisement
Guest User

temp

a guest
Nov 12th, 2019
378
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.90 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. int const nax = 1e5 + 10;
  5. ll sum, f[nax];
  6. ll calc(int x, int n){
  7.     n -= x - 1;
  8.     int s = n / x;
  9.     int res = n - x * s;
  10.     ll toReturn = 0;
  11.     toReturn += 1LL * x * s * (s + 1); /// (1 + ... + s) * x
  12.     toReturn >>= 1;
  13.     n += x - 1;
  14.     return toReturn + 1LL * res * (s + 1);
  15. }
  16. int n;
  17.  
  18.  
  19. int main(){
  20.     scanf("%d", &n);
  21.     for(int a = n ; a >= 1 ; a -- ){
  22.         ll toMinus = 0;
  23.         ll toAdd = 0;
  24.         for(int b = a ; b <= n ; b += a){
  25.             toMinus += f[b];
  26.             /// b = k  * a
  27.             /// a * k , a * (k + 1) , ... , a * sth
  28.             /// divide by a * k
  29.             /// -> [k / k] -> sth / k
  30.             int sth = n / a;
  31.             int k = b / a;
  32.             toAdd += calc(k, sth);
  33.         }
  34.         toAdd -= toMinus;
  35.         f[a] = toAdd;
  36.     }
  37.     printf("%lld\n", f[1]);
  38. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement