PROBLEM LINK:
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Conics, Counting
PROBLEM:
We need to find the number of pairs of a, b and c such that
- a\in[1, A] , b\in[1, B], c\in[1, C].
- ax^2+2bxy+cy^2 > x^2+y^2 holds for \forall x,y\in(-\infty, 0)\cup(0,+\infty) .
STRATEGY
First, let’s try to simplify the above equation, on simplifying we’ll get->
let \Theta = (a-1)x^2+2bxy+(c-1)y^2 > 0.
This is an equation for conics. Note that for \Theta to hold true, the equation must correspond to that of an ellipse with both r_{1} = r_{2} = 0. For \Theta to be an ellipse, it must satisfy Q^2 - 4*P*R < 0 where P=a-1, Q=2b, R=c-1. We get the relation b^2 < (a-1)(c-1).
Now our question reduces to finding the number of pairs of a and c which when multiplied give the result as greater than b^2.
Let’s try to find the number of pairs of a, c such that a*c<=b^2. The solution to this problem is simply the summation of the following series->
\phi = \sum_{k=1}^N \lfloor N/k \rfloor (try it yourself)
However, using this takes \theta(N) time which is too much. We can reduce \phi as follows using a neat counting trick →
let \phi' = 2*\sum_{k=1}^ {\lfloor\sqrt[2]N \rfloor} \lfloor N/k \rfloor + \lfloor\sqrt[2]N \rfloor^2
You can arrive at this result by making possible pairs yourself and choosing only up to \sqrt[2]N of the pairs. However, we cannot use this formula directly as there’s an upper bound on A and C whereas there’s no bound in the formula. We’ll call this summation root_summation. You can look up how it’s implemented in the code given below. The time complexity of this summation would be \theta(\sqrt[2]N).
ALGORITHM
A := A - 1;
C := C - 1;
let total = A*C;
let sum = 0;
for b in B {
sum = (sum + total - root_summation(b*b, A, C)) % MOD;
}
CODE
#include <iostream>
#include <cmath>
long long MODULO = pow(10, 9) + 7;
int main() {
// freopen("input.txt", "r", stdin);
int T;
scanf("%d", &T);
while (T--) {
long long A, B, C;
scanf("%lld %lld %lld", &A, &B, &C);
A -= 1; C-= 1;
long long count = 0;
long long total = A*C; // TAKE MOD
for (int i=1; i<=B; i++) {
int p = i*i;
int max_range;
int limiting;
int full_range;
bool use_rootsum = false;
if (A < C) {
if (A <= i) {
max_range = A;
limiting = C;
full_range = A;
} else {
max_range = i;
full_range = C;
limiting = A;
use_rootsum = true;
}
} else {
if (C <= i) {
max_range = C;
full_range = C;
limiting = A;
} else {
max_range = i;
full_range = A;
limiting = C;
use_rootsum = true;
}
}
long long sum = 0;
long long diff = 0;
for (int a=1; a<=max_range; a++) {;
diff = diff + std::max(0, (std::min(full_range, p/a) - limiting));
sum = sum + std::min(limiting, p/a);
}
sum = sum + use_rootsum*(sum - p + diff);
count = (count + total-sum) % MODULO;
}
printf("%lld\n", count);
}
return 0;
}
TIME COMPLEXITY
The time complexity of the algorithm discussed in this editorial is O(N*\sqrt[2]N) per test case.