#PROBLEM LINK:
contest
#PREREQUISITES:
Basic Mathematics, Ad-hoc.
#Problem:
Given a number N, find the sum of all products x*y such that N/x = y (Integer Division).
#Brute-force:
The simplest brute force solution involves iterating over all possible values of x and finding the corresponding value of y, and updating the running sum by adding x * y.
Unfortunately, this does not pass as the overall time complexity is O(T * N).
#The Pattern:
If you tried to simulate the brute-force, you might observe the intriguing pattern of finding a lot of 1’s (approx N / 2) at the end.
The trick is to notice that many numbers, not only 1, are going to be repeated.
Let us consider an example of N = 10:
x = 1, y = 10
x = 2, y = 5
x = 3, y = 3
x = 4, y = 2
x = 5, y = 2
x = 6, y = 1
x = 7, y = 1
x = 8, y = 1
x = 9, y = 1
x = 10, y = 1
Observation 1: Note that not only 1, but 2 is also repeated. Rather, on simulating even bigger integers, you must notice that no more than O(sqrt(N)) distinct integers will ever occur.
Observation 2: All the repetitions will always to occuring together in a sequence such that they form an interval.
Now, we are getting closer to the solution, we can create chunks for each value of y and break our sum operation as follows:
10 * 1 + 5 * 2 + 3 * 3 + 2 * (4 + 5) + 1 * (6 + 7 + 8 + 9 + 10)
So, for each value y, if we find the lowest value of x (say, lo) and highest value of x(say, hi), we can find the entire summation in O(sqrt(N)).
I’d recommend you to go back to the problem and try to solve it with this much information only.
So as to complete the solution, we must find the way to compute values of lo and hi, for y = 1, lo = 6 and hi = 10
for y = 2, lo = 4 and hi = 5
for y = 3, lo = 3 and hi = 3
The other crucial observation is to notice that each pair of values (x,y) must have at least one value in [1, sqrt(N)].
Thus, we need not process the values of y any furthur…!!
But, aren’t we missing out on the pairs (1, 10) and (2, 5) ?
Well, these are exactly the pairs that have x * y = N, so we can compute them on-the-fly when y = 1 and y = 2. You might need to pay some attention while implementating, so as to avoid counting sqrt(N) twice and also to handle MOD correctly!!
#include <stdio.h>
#include <math.h>
#define ull unsigned long long
#define mod 1000000007
ull sum(ull n) {
ull res = 0;
if(n&1) {
res = (n+1)>>1;
res = (res * n);
} else {
res = n>>1;
res = (res * (n+1));
}
return res;
}
ull solve(ull n) {
ull srt = sqrt(n),x,y,add;
ull res = 0;
int i;
for (i = 1; i <= srt; ++i)
{
res = (res + ((n/i)*i));
if(res > mod)
res %= mod;
}
for (i = n/srt; i > 1; --i)
{
x = n/i;
y = n/(i-1);
add = (i-1) * (sum(y) - sum(x));
res = (res + add);
if(res > mod)
res %= mod;
}
return res;
}
template<class T> inline void scan(T&x) {
x=0;bool fu=0; char c;do{c=getchar_unlocked();}while(c<=32);
if(c=='-') fu=1,c=getchar_unlocked(); while(c>32){x=x*10+c-'0';c=getchar_unlocked();}
if(fu) x=-x;
}
inline void fastWrite(unsigned a)
{
char snum[12];
int i=0;
do
{
snum[i++]=a%10+48;
a=a/10;
}
while (a);
i=i-1;
while (i>=0)
putchar_unlocked(snum[i--]);
putchar_unlocked('\n');
}
int main(int argc, char const *argv[])
{
int t;ull n;
scan(t);
while(t--) {
scan(n);
fastWrite(solve(n));
}
return 0;
}