Advertisement
fooker

cses_sum_of_divisors

May 12th, 2023
129
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.52 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. const ll nmax=1e9+7;
  5. ll int_sqrt (ll x) {
  6.   ll ans = 0;
  7.   for (ll k = 1LL << 30; k != 0; k /= 2) {
  8.     if ((ans + k) * (ans + k) <= x) {
  9.       ans += k;
  10.     }
  11.   }
  12.   return ans;
  13. }
  14. int main()
  15. {
  16.     ll n;
  17.     cin>>n;
  18.     ll sq=int_sqrt(n);
  19.     ll ans=0;
  20.     for (ll i=1; i*i<=n; i++){
  21.         ans+=((i*(n/i))%nmax+(((n/i)*(1+n/i))/2)%nmax)%nmax;
  22.     }
  23.     ans=(ans+nmax-(((((sq%nmax)*((sq+1)%nmax))/2)%nmax)*sq)%nmax)%nmax;
  24.     cout<<ans<<"\n";
  25. }
  26.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement