PCJ18G - Editorial

editorial
, , , , ,
1

PROBLEM LINK:

Practice
Contest

Author Madhav Sainanee
Tester Prakhar Gupta
Editorialist Madhav Sainanee

DIFFICULTY:

EASY-MEDIUM

PREREQUISTES:

Basic number theory, Modular inverse

PROBLEM:

You are required to find the number of unique rectangles which lie fully under a hyperbola given by xy \leq n, given x, y > 0.

QUICK EXPLANATION:

For every value of x, our value of y is \lfloor\frac{n}{x}\rfloor. So, for every x, we can number of rectangles with top right corner as (x, y) is x \times y \times (y+1) with y = \lfloor\frac{n}{x}\rfloor

Since, for this we’d have to traverse all values of n, we need a better approach. Since for x > \sqrt{n}, there are only \sqrt{n} unique values of y. So,
We can find unique values of y and add y \times (y+1) \times (f(r) - f(l-1)) \text{ } to our answer where f(a) is sum of all values of x starting from 1 to \lfloor\frac{n}{a}\rfloor, r is \lfloor\frac{n}{y}\rfloor and l = \lfloor\frac{n}{(y+1)}\rfloor + 1

EXPLANATION

Let us start with counting rectangles with top corners as (x, \lfloor\frac{n}{x}\rfloor) for x \leq \sqrt{n}

for(int i = 1; i <= sqrt(n); i++)
{
	int y = n/i;  
	int temp = takemod(takemod(y)*takemod(y+1))*modinv(2);
	temp = takemod(temp);
	temp *= i;
	temp = takemod(temp);
	res += temp;
	res = takemod(res);
}

Now, for x > \sqrt{n}, since there are only \sqrt{n} unique values of y, let us find corresponding ranges for every y.

int start = n/((int)sqrtl(n) + 1);
int m = sqrtl(n);
pair<int, int> intervals[m+5];
intervals[start].ff = sqrtl(n)+1;
for(int i = start; i >= 1; i--)
{
	if(i == start)
	{
		intervals[i].ss = n/(i);
		continue;
	}
	intervals[i].ff = intervals[i+1].ss + 1;
	intervals[i].ss = n/i;
}

Now that we have intervals, f(a) can be calculated as \frac{a \times (a+1)}{2}

for(int i = 1; i <= start; i++)
{
	int temp = (i*(i+1))/2;
	int l = intervals[i].ff;
	int r = intervals[i].ss;
	l--;
	int temp2 = takemod(takemod(r)*takemod(r+1))*modinv(2);
	int temp3 = takemod(takemod(l)*takemod(l+1))*modinv(2);
	temp2 = takemod(temp2);
	temp3 = takemod(temp3);
	int x = takemod(temp2-temp3);
	temp = takemod(temp);
	res += (x*temp);
	res = takemod(res);
}

Then we can simply print the result.

Note: Functions used-

int takemod(int a){
	return ((a%mod)+mod)%mod;
}

int fast_exp(int base, int expo) {
	int res=1;
	while(expo>0) {
		if(expo&1) res=(res*base)%mod;
		base=(base*base)%mod;
		expo>>=1;
	}
	return res;
}

int modinv(int a){
	return takemod(fast_exp(takemod(a), mod-2));
}

Complexity: The time complexity is O(\sqrt{N}) per test case.

AUTHOR’S SOLUTION:

Author’s solution can be found here

2

#include<stdio.h>
#include<math.h>
#define ll long long int
#define M 1000000007
int main()
{
int t;
scanf("%d",&t);
while(t–)
{
ll n,i,ans=0,x;
scanf("%lld",&n);
x=(ll)floor(sqrt(n));
for(i=1;i<=x;i++)
{
ll val = i;
val = ((val%M)((i + (ll)floor(n/i))%M))%M;
val = ((val%M)((1 + (ll)floor(n/i) - i)%M))%M;
ans = (ans%M + val%M)%M;
}
ans = (ans%M - ((x*(x+1)(2x + 1))/6)%M + M)%M;
printf("%lld\n",ans);
}
return 0;
}