3

This is a codeforces question, where we have to calculate the sum of $N\bmod i$ modulo $10^9 + 7$ where $i$ goes from $1$ to $M$.

$N$ and $M$ are very large values about $10^{13}$.

They have provided an editorial for this question, but I dont understand it completely.

I understand why they rewrote the question like this $$mn - \sum_{n=1}^{\min(n,m)} \left \lfloor{\frac{n}{i}}\right \rfloor i$$

I also understand the inequality they wrote ( which was obtained from the fact that factors of a number are less than or equal to its square root since floor(n/i) is a factor of n) $$ \left \lfloor{\frac{n}{i}}\right \rfloor <= (n)^{1/2} $$ But I dont understand anything that they did further, what are the two sums the are talking about and how did the reduce the summation? Any help is appreciated :)

miracle173
  • 11,049
karun
  • 45
  • 1
  • 3

2 Answers2

3

A very similar problem is present on spoj: SUMPRO

C++ implementation to find the summation of i*(n/i) from i=1 to n for t number of testcases is given below:

#include<iostream>
#include<cmath>
using namespace std;
int main()
{
    long long t,n,sqrt_n;
    long long mod = 1000000007;
    cin>>t;
    while(t--){
    cin>>n;
    sqrt_n = sqrt(n);
    long long sum = 0;
    //finding summation of N/i *i from i=1 to sqrt(N)
    for(long long i=1; i<=sqrt_n; i++)
        sum = sum + (n/i)*i;
    // after i=sqrt(N), there is no need to iterate further bcoz value of N/i will either decrease by 1 or remain same
    for(long long i=n/sqrt_n-1; i>=1; i--)
    {
        long long lower_limit = n/(i+1);
        long long upper_limit = n/i;
        long long tmp = ((upper_limit*(upper_limit+1))/2 - (lower_limit*(lower_limit+1))/2);
        sum = sum + tmp*i;
    }
    cout<<sum%mod<<endl;
}
    return 0;
}

Complexity of this solution is O(sqrt(N)) for each testcase. If you wanna print the actual sum, don't perform the modulo operation in cout<<sum%mod<<endl.

Ahsan Kamal
  • 46
  • 4
2

It's not too difficult to do this reasonably fast. There is of course the problem that if N, M are around 10^13, you are adding up an awful lot of very large numbers. The result will not be able to fit int 64 bits, so that is something you need to handle. I'll leave that up to you.

N % i equals N - (N / i) * i, where N / i is an integer division, rounded down to the nearest integer. The simple trick that you need is that when i is large, there will be several or even many values of i where N / i gives the same value.

First we simplify: If N = 0 then f (N, M) = 0. If M ≥ N: N % i = N if i > N, N % i = 0 if i = N. Therefore f (N, M) = (M - N) * N + f (N, N - 1) if M ≥ N. If M is small we just calculate the sum in the obvious way, so now we have N > M >> 0. We have N / i ≥ 1.

Choose an integer K a bit below the square root of N: I'd choose K = floor (sqrt (N / 4)). We add separately for the case N / i ≥ K and N / i < K. N / i ≥ K <=> i ≤ N / K. So first add N % i for 1 ≤ i ≤ min (M, N / K). If M ≤ N / K we are done.

Now the cases where N / i < K: We don't do a loop for the values i, but for the distinct values k = N / i, for 1 ≤ k < K. For each k, determine the values i where N / i = k: We have N / i ≥ k <=> i ≤ N / k. On the other hand, N / i < k+1 <=> i > N / (k+1), so N / (k+1) < i ≤ N / k. We also need i ≤ M, so we add nothing if N / (k + 1) ≥ M. If N / (k + 1) < M, then we add for N / (k + 1) < i ≤ MIN (N / k, M). Let min = N / (k + 1) + 1, max = MIN (N / k, M), then we add for min ≤ i ≤ max.

The value to add each time is N % i = N - (N / i) * i = N - k*i. The sum is (max - min + 1) * ((N - kmin) + (N - kmax)) / 2.

So the trick is finding many values i where N/i is the same and all the values N % i can be added using a simple formula. We only add at most N/K + K values, about O (sqrt (N)).

gnasher729
  • 10,113