Advertisement
RaFiN_

Sum of Remainders cf-616E

Jul 12th, 2020
1,140
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.73 KB | None | 0 0
  1.  
  2.  
  3. ll pk;
  4.  
  5. ll sum(ll n){
  6.     return (((n%mod)*((n+1ll)%mod))%mod * pk)%mod;
  7. }
  8.  
  9. int main()
  10. {
  11.     booster()
  12.     //read("input.txt");
  13.     ll n,m;
  14.     pk = BigMod<ll>(2,mod-2);
  15.     cin >> n >> m;ll tot = 0;
  16.     ull x = n % mod;
  17.     ull y = m % mod;
  18.     ull ans = (x * y)%mod;
  19.     ll mn = min(n,m);
  20.     m = min(n,m);
  21.     for(ll i = 1;i*i<=n;i++){
  22.         ll le = n / i,ri = n / (i+1);
  23.         le = min(le,m);
  24.         if(ri>=le) continue;
  25.         tot = ((tot + (i * ((sum(le) - sum(ri))%mod + mod )%mod )%mod))%mod;
  26.         tot %= mod;
  27.         mn = ri;
  28.     }
  29.     for(ll i = 1;i<=mn;i++) {
  30.         tot = (tot + ((n/i)%mod * i)%mod)%mod;
  31.         tot %= mod;
  32.     }
  33.     cout << (ans - tot + mod) % mod;
  34.  
  35.     return 0;
  36. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement