Help in sum of divisors - CSES

Problem
My approach:
The answer is \displaystyle\sum_{i \ = \ 1}^{n} i \ \Big\lfloor\dfrac{n}{i}\Big\rfloor\ \text{mod}\ 10^9+7.
A linear approach will time out.
Notice that \Big\lfloor\dfrac{n}{i}\Big\rfloor = 1,\ \forall \ i > \sqrt{n}. Let’s say \lfloor\sqrt{n}\rfloor = i for simplicity.
We have an AP of (n-i+1) terms starting from (i+1) to n. It’s sum will be \dfrac{n-i+1}{2} \Big[2i+(n-i)\Big] = (n-i+1)(n+i)(2^{-1}).
So the answer is \Bigg(\displaystyle\sum_{k \ = \ 1}^{i} k \ \Big\lfloor\dfrac{n}{k}\Big\rfloor\Bigg) + (n-i+1)(n+i)(2^{-1}) all \text{mod} \ 10^9+7.
My code:

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 1e9+7;

int exp(int x, int y, int p)
{
    x %= p;
    int res = 1LL;
    while (y > 0)
    {
        if (y & 1) res = (res * x) % p;
        y >>= 1;
        x = (x * x) % p;
    }
    return res;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, ans = 0;
    cin >> n;
    int i;
    for (i = 1; i*i <= n; ++i)
    {
        ans += (i*(n/i));
        ans %= mod;
    }
    ans += (((((n-i+1)%mod)*((n+i)%mod))%mod)*(exp(2, mod-2, mod)%mod))%mod;
    cout << ans << '\n';
}

This passes the sample test case but gets WA for larger inputs. Although I’m not sure, it might be the modular inverse. Please let me know where I’m wrong.

How is \bigg \lfloor \dfrac{n}{i}\bigg \rfloor = 1 \; \forall \; i > \sqrt n ?
Take n = 10, then i = \lceil \sqrt{10}\rceil = 3. But \bigg \lfloor \dfrac{10}{4} \bigg \rfloor= 2?
And did you mean i = \lfloor \sqrt n \rfloor or i = \lceil \sqrt n \rceil?

P.S: How do you type floor and ceil in LaTeX? :3

1 Like

\lfloor x \rfloor and \lceil x \rceil

1 Like

How to write n/i btw?

Use $ to enclose your LaTeX typescript.

$ n $ \rightarrow n

2 Likes

Thanks, I got confused with n^{\frac{1}{2}} and \dfrac{n}{2}.
Also, \lceil n \rceil and \lfloor n \rfloor can be used.

1 Like

Is there any blog about this how to write different things?

@aneee004 I forgot to mention that if x is a fraction, use \Big\lceil \dfrac{...}{...} \Big\rceil.

1 Like

I use stackexchange.

1 Like

Here in CodeChef, we have three types of formats.

  1. The “`”. Use this to make things look like this (monospaced font).
  2. The “```”. Enclose your code between this, to colour format it.
cout << "Hello World";
  1. And then the most important one, LaTeX. You can look up the symbols here. Anything enclose with a $ will be read in LaTeX.
3 Likes

Yess! I’m aware of \bigg or \Big and \dfrac. I use LaTeX for almost all my assignments :P. I was fed up with \frac. It just crowds things up and looks ew. I was so satisfied when I discovered \dfrac xD.

2 Likes