Help in sum of divisors - CSES

help
1

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.

2

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
3

\lfloor x \rfloor and \lceil x \rceil

1 Like
4

How to write n/i btw?

5

Use $ to enclose your LaTeX typescript.

$ n $ \rightarrow n

2 Likes
6

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
7

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

8

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

1 Like
9

I use stackexchange.

1 Like
10

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
11

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