 # PCJ18G - Editorial

Tester Prakhar Gupta

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

1 Like

#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;
}