PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: pols_agyi_pols
Tester: kingmessi
Editorialist: iceknight1093
DIFFICULTY:
Medium
PREREQUISITES:
Mobius function
PROBLEM:
Given a value Z, count the number of pairs (X, Y) such that 1 \le X, Y \le Z and \text{lcm}(X, Y) \gt Z.
In this version, \sum Z \le 10^9.
EXPLANATION:
From the easy version, we already know that the solution is as follows:
- Define f(N) to be the number of ordered pairs of positive integers whose LCM equals N.
- Then the answer is Z^2 - \sum_{N=1}^Z f(N).
The easy version allowed us to compute f(N) in \mathcal{O}(\log N) time for each 1 \le N \le Z, but we can no longer afford to do that.
There are a couple of ways to optimize this computation.
Below is the simpler one; requiring a bit less machinery.
Recall that our aim is really to compute the number of pairs with LCM \le Z.
Let’s rewrite this a bit.
Consider two integers X and Y, and let g = \gcd(X, Y).
Then, we have \text{lcm}(X, Y) = \frac{XY}{g} = g\cdot u\cdot v, where u = \frac{X}{g} and v = \frac{Y}{g}.
Note that \gcd(u, v) = 1.
This also goes the other way: if we take any three integers g, u, v such that g\cdot u\cdot v \le Z and \gcd(u, v) = 1, then we get the unique pair (g\cdot u, g\cdot v) with LCM \le Z.
So, our goal is to count such triplets.
The hard part here is dealing with the \gcd(u, v) = 1 constraint.
We can write out what we want to compute as
where the expression [P] refers to the Iverson bracket, which evaluates to 1 if the statement P is true and 0 otherwise.
Luckily for us, there happens to be a rather well-known number-theoretic function with a similar property - the Mobius function!
Specifically, we have
That is, the sum of Mobius values of the divisors of N evaluates to 1 if N = 1, and evaluates to 0 otherwise.
This allows us to write the summation above as
To compute this double summation, we can do the following:
- Fix the value of d and compute \mu(d)
- Then, compute the number of triplets (g, u, v) such that g\cdot u \cdot v \le Z and d \mid \gcd(u, v).
- Add this count multiplied by \mu(d) to the answer.
What remains is doing this quickly.
Suppose we fix the value of d. Computing \mu(d) is not too hard from the prime factorization of d, so only the number of valid triplets (g, u, v) needs to be computed quickly.
We need d\mid \gcd(u, v), which is equivalent to saying that d divides both u and v.
So, let’s write u = d\cdot u' and v = d\cdot v'.
We can now choose u' and v' to be any positive integers.
Plugging this back into g\cdot u\cdot v \le Z, we obtain the inequality g\cdot d^2 \cdot u'\cdot v' \le Z.
Since d is fixed and all of g, u', v' are now unconstrained, we really just want the number of triplets whose product doesn’t exceed \frac{Z}{d^2}.
So, we have with us a subproblem: let M = \frac{Z}{d^2}, and we want to count the number of ordered triplets of integers with product not exceeding M.
This can be done in \mathcal{O}(M^{3/4}) time.
How?
We want to count g\cdot u'\cdot v' \le M.
Suppose we fix the value of g, so that the problem reduces to counting the number of pairs of integers with product \le \frac{M}{g}.
This is simply the summation \sum_{i=1}^P \left\lfloor \frac{P}{i} \right\rfloor where P = \left\lfloor \frac{M}{g} \right\rfloor.Note that this summation can be computed in \mathcal{O}(\sqrt P) time, utilizing the fact that there are only \mathcal{O}(\sqrt P) distinct values of \left\lfloor \frac{P}{i} \right\rfloor.
However, there are similarly only \mathcal{O}(\sqrt M) distinct values of \left\lfloor \frac{M}{g} \right\rfloor possible as well.
For g \gt \sqrt {M}, we have P \le \sqrt M and so \sqrt P \le M^{1/4}.
Thus, for each “large” g the work we do is bounded by M^{1/4}, and since we need to work with only at most \sqrt M such large g, the total work is bounded by \mathcal{O}(M^{3/4}) here.For g \le \sqrt M, the work we do is given by
\sum_{g \le \sqrt M} \sqrt{\frac{M}{g}} = \sqrt{M} \cdot \sum_{g \le \sqrt M} \frac{1}{\sqrt g}It can be proved (using telescoping sums) that for any integer x \ge 2, we have
\sqrt{x} \lt \sum_{i=1}^x \frac{1}{\sqrt x} \lt \sqrt{2x}In particular, this means \displaystyle\sum_{g \le \sqrt M} \frac{1}{\sqrt g} \le 2\cdot M^{1/4}.
So, the total work we do in the second case is also \mathcal{O}(M^{3/4}).
Thus, with d fixed, we can compute the number of triples in
time.
Clearly, we also need d^2 \le Z, so it’s enough to consider d \le \sqrt Z.
Thus, the total work we do is
This, however, is just \mathcal{O}(Z^{3/4}) work, because of the well-known fact that the sum \displaystyle\sum_{n \ge 1} \frac{1}{n^p} converges for p \gt 1.
In particular, we have p = \frac{3}{2}, where the infinite sum evaluates to about 2.61 so the constant factor isn’t terribly high either.
So, we do \mathcal{O}(Z^{3/4}) work per testcase to compute the answer.
Further, since we deal with only d \le \sqrt{10^9} \le 10^5 and these are the only values of \mu(d) that are needed, we can simply use a sieve to precompute all the Mobius values till 10^5 and look them up as needed!
There can be upto 10^6 testcases, but since \sum Z is bounded by 10^9 the worst case is 10^6 tests of Z = 1000, where \sum Z^{3/4} ends up being a bit less than 2\cdot 10^8, which, along with the high time limit, is good enough (despite the hidden constants.)
There also exists a solution with better complexity but more machinery - utilizing Dirichlet convolutions.
The function f(N) = number of pairs with LCM N turns out to be a multiplicative function with nice enough properties (in particular, it equals \tau(N^2) where \tau is the divisor function), which is what allows for Dirichlet convolutions to be used to compute its prefix sum.
Figuring out the details is left as an exercise to the reader 
The complexity here is \mathcal{O}(Z^{2/3}) per test, which is of course a lot better and will comfortably pass.
TIME COMPLEXITY:
\mathcal{O}(Z^{3/4}) or \mathcal{O}(Z^{2/3}) per testcase.
CODE:
Tester's code (C++)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5+5;
int mobius[N];
int smz = 0;
void solve(){
int z;
cin >> z;
int bad = 0;
for(int i = 1;i*i <= z;i++){
int n = z/(i*i);
int D = 0;
for(int j = 1;j <= n;){
int f = n/j;
int tot = 0,ls;
for(int k = 1;k*k <= f;k++){
tot += f/k;ls = (k*k);
}
tot = 2*tot - ls;
D += tot * (n/f - j + 1);
j = n/f + 1;
}
bad += mobius[i]*D;
}
cout << z*z - bad << "\n";
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
mobius[1] = -1;
for (int i = 1; i < N; i++) {
if (mobius[i]) {
mobius[i] = -mobius[i];
for (int j = 2 * i; j < N; j += i) { mobius[j] += mobius[i]; }
}
}
while(t--)
solve();
return 0;
}