Statement:
Given two integer $$$n, k, p$$$, $$$(1 \leq k \leq n < p)$$$.
Count the number of array $$$a[]$$$ of size $$$k$$$ that satisfied
- $$$1 \leq a_1 < a_2 < \dots < a_k \leq n$$$
- $$$a_i \times a_j$$$ is perfect square $$$\forall 1 \leq i < j \leq n$$$
Since the number can be big, output it under modulo $$$p$$$.
Solve for k = 1
The answer just simply be $$$n$$$
Solve for k = 2
We need to count the number of pair $$$(a, b)$$$ that $$$1 \leq a < b \leq n$$$ and $$$a \times b$$$ is perfect square
Every positive integer $$$x$$$ can be represent uniquely as $$$x = u \times p^2$$$ for some positive integer $$$u, p$$$ and $$$u$$$ as small as possible ($$$u$$$ is squarefree number)
Let represent $$$x = u \times p^2$$$ and $$$y = v \times q^2$$$ (still, minimum $$$u$$$, $$$v$$$ ofcourse)
We can easily proove that $$$x \times y$$$ is a perfect square if and if only $$$u = v$$$
So for a fixed squarefree number $$$u$$$. You just need to count the number of ways to choose $$$p^2$$$
Therefore the answer just simply be
So about the complexity....
For the implementation using factorization. It is ofcourse $$$O(n log log n)$$$, you can easily proove it. As it just related to the sum of inversion of primes
For the 2 implementations below: The complexity is $$$O\left(\underset{squarefree p \leq n}{\Large \Sigma} \left \lfloor \frac{n}{p^2} \right \rfloor \right)$$$
Solve for general k
Using the same logic above, we can easily solve the problem with combinatorics
A better solution for k = 2
In this approach, instead of fixing $$$u$$$ as a squarefree and count $$$p^2$$$. We do the reverse, let count the number of way to select $$$u$$$ as we fix $$$p^2$$$.
Normaly, it will still lead you to $$$O(n)$$$ solution:
Let $$$f(n)$$$ is the number of $$$(a, b)$$$ that $$$1 \leq a < b \leq n$$$ and $$$(a, b, n)$$$ is a three-term geometric progression
Why do we need this function, well. You see since $$$(a, b, n)$$$ form a three-term geometric progression. Therefore we have $$$b^2 = an$$$.
Let $$$F(N) = \overset{n}{\underset{p=1}{\Large \Sigma}} f(p)$$$
It is not hard to proove that $$$F(N)$$$ will be our answer as we count over all possible squarefree $$$u$$$ for every fixed $$$p^2$$$
Let $$$g(n)$$$ is the number of $$$(a, b)$$$ that $$$1 \leq a \leq b \leq n$$$ and $$$(a, b, n)$$$ is a three-term geometric progression
It is no hard to proove that $$$g(n) = f(n) - 1$$$
But this interesting sequence $$$g(n)$$$ is A000188
This sequence have many property, such as
- Number of solutions to $$$x^2 \equiv 0 \pmod n$$$
- Square root of largest square dividing $$$n$$$
- Max $$$gcd \left(d, \frac{n}{d}\right)$$$ for all divisor $$$d$$$.
- bla bla bla
Well, actually to make the problem whole easier, I gonna skip all the proofs (still, you can use the link in the sequence to prove). And use this property
$$$g(n) = \underset{d^2 | n}{\Large \Sigma} \phi(d)$$$
Then we have
$$$F(N)$$$ $$$= \overset{n}{\underset{p=1}{\Large \Sigma}} f(p)$$$ $$$= \overset{n}{\underset{p=2}{\Large \Sigma}} g(p)$$$ $$$= \overset{n}{\underset{p=2}{\Large \Sigma}} \underset{d^2 | p}{\Large \Sigma} \phi(d)$$$ $$$= \overset{\left \lfloor \sqrt{n} \right \rfloor}{\underset{p=2}{\Large \Sigma}} \underset{1 \leq u \times p^2 \leq n}{\Large \Sigma} \phi(p)$$$ $$$= \overset{\left \lfloor \sqrt{n} \right \rfloor}{\underset{p=2}{\Large \Sigma}} \phi(p) \times \left \lfloor \frac{n}{p^2} \right \rfloor$$$
Well, you can sieve $$$phi(p)$$$ for all $$$2 \leq p \leq \sqrt{n}$$$ in $$$O\left(sqrt{n} \log \log \sqrt{n} \right)$$$ or improve it with linear sieve to $$$O(sqrt{n})$$$
Therefore you can solve the whole problem in $$$O(\sqrt{n})$$$.
Yet this paper also takes you to something similar.
My question
A: Can we also use phi function or something similar to solve for general $$$k$$$ in $$$O(\sqrt{n})$$$ ?
B: Can we also solve the problem when $$$a_i \leq a_j (\forall\ i < j)$$$ and no longer $$$a_i < a_j (\forall\ i < j)$$$ ?
C: Can we solve the problem where there is no restriction between $$$k, n, p$$$ ?
D: Can we solve for negative number, whereas $$$-n \leq a_1 < a_2 < \dots < a_k < n$$$
E: Can we solve for a specific range, wehreas $$$L \leq a_1 < a_2 < \dots < a_k < R$$$
F: Can we solve for cube product effectively ?