[Tutorial] An interesting counting problem related to square product

Revision en32, by SPyofcode, 2021-10-30 19:42:58

The statement:

Given three integers $$$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$$$.

For convenient, you can assume $$$p$$$ is a large constant prime $$$10^9 + 7$$$

Yet you can submit the problem for $$$k = 3$$$ here.






Extra Tasks

Solved A: Can we also use phi function or something similar to solve for $$$k = 3$$$ in $$$O(\sqrt{n})$$$ ?

Solved B: Can we also use phi function or something similar to solve for general $$$k$$$ in $$$O(\sqrt{n})$$$ ?

Solved C: Can we also solve the problem where there can be duplicate: $$$a_i \leq a_j\ (\forall\ i < j)$$$ and no longer $$$a_i < a_j (\forall\ i < j)$$$ ?

Solved D: Can we solve the problem where there is no restriction between $$$k, n, p$$$ ?

E: Can we solve for negative integers, whereas $$$-n \leq a_1 < a_2 < \dots < a_k \leq n$$$ ?

F: Can we solve for a specific range, whereas $$$L \leq a_1 < a_2 < \dots < a_k \leq R$$$ ?

G: Can we solve for cube product $$$a_i \times a_j \times a_k$$$ effectively ?

H: Can we solve if it is given $$$n$$$ and queries for $$$k$$$ ?

I: Can we solve if it is given $$$k$$$ and queries for $$$n$$$ ?

J: Can we also solve the problem where there are no order: Just simply $$$1 \leq a_i \leq n$$$ ?

K: Can we solve for $$$q$$$-product $$$a_{i_1} \times a_{i_2} \times \dots \times a_{i_q} = x^q$$$ (for given constant $$$q$$$) ?

M: Given $$$0 \leq \delta \leq n$$$, can we also solve the problem when $$$1 \leq a_1 \leq a_1 + \delta + \leq a_2 \leq a_2 + \delta \leq \dots \leq a_k \leq n$$$ ?

*Marked as solved only if tested with atleast $$$10^6$$$ queries






Solution for k = 1

The answer just simply be $$$n$$$






Solution for k = 2


Algorithm

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$$$.

The answer will be the sum of such ways for each fixed $$$u$$$.


Implementation

Implementation using factorization
Implementation 1
Implementation 2
Implementation related to Möbius function

Complexity

So about the complexity....

For the implementation using factorization, it is $$$O(n \log n)$$$.

Hint 1
Hint 2
Proof
Bonus

For the 2 implementations below, the complexity is linear.

Hint 1
Hint 2
Hint 3
Hint 4
Proof

For the last implementation, the complexity is Linear

Hint 1
Hint 2
Proof





Solution for general k

Using the same logic above, we can easily solve the problem.

Now you face up with familliar binomial coefficient problem

This implementation here is using the assumption of $$$p$$$ prime and $$$p > max(n, k)$$$

You can still solve the problem for squarefree $$$p$$$ using lucas and CRT

Yet just let things simple as we only focus on the counting problem, we will assume $$$p$$$ is a large constant prime.

O(n) solution





A better solution for k = 2


Idea

In the above approach, we fix $$$u$$$ as a squarefree and count $$$p^2$$$.

But what if I fix $$$p^2$$$ to count $$$u$$$ instead ?

Yet you can see that the first loop now is $$$O(\sqrt{n})$$$, but it will still $$$O(n)$$$ total because of the second loop

Swap for loop implementation

Approach

Let $$$f(n)$$$ is the number of pair $$$(a, b)$$$ that $$$1 \leq a < b \leq n$$$ and $$$(a, b, n)$$$ is a three-term geometric progression.

Let $$$g(n)$$$ is the number of pair $$$(a, b)$$$ that $$$1 \leq a \leq b \leq n$$$ and $$$(a, b, n)$$$ is a three-term geometric progression.

Let $$$F(n) = \overset{n}{\underset{p=1}{\Large \Sigma}} f(p)$$$.

But why do we need these functions anyway

So it is no hard to prove that $$$g(n) = f(n) + 1$$$.

This interesting sequence $$$g(n)$$$ is A000188, having many properties, 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$$$.

Well, to make the problem whole easier, I gonna skip all the proofs to use this property (still, you can use the link in the sequence for references).

$$$g(n) = \underset{d^2 | n}{\Large \Sigma} \phi(d)$$$.

From this property, we can solve the problem in $$$O(\sqrt{n})$$$.

Hint 1
Hint 2
Hint 3
Hint 4
Solution

Yet this paper also takes you to something similar.


Implementation

O(sqrt n log log sqrt n) solution
O(sqrt) solution





A better solution for general k

Extra task A, B


Algorithm

As what clyring decribed here

Let $$$f_k(n)$$$ is the number of set $$$(a_1, a_2, \dots, a_k, n)$$$ that $$$1 \leq a_1 < a_2 < \dots < a_k \leq n$$$ and $$$(a_1, a_2, \dots, a_k, n)$$$ is a $$$(k+1)$$$-term geometric progression.

Let $$$g_k(n)$$$ is the number of set $$$(a_1, a_2, \dots, a_k, n)$$$ that $$$1 \leq a_1 \leq a_2 \leq \dots \leq a_k \leq n$$$ and $$$(a_1, a_2, \dots, a_k, n)$$$ is a $$$(k+1)$$$-term geometric progression.

Let $$$F_k(n) = \overset{n}{\underset{p=1}{\Large \Sigma}} f_k(p)$$$.

Let $$$s_k(n)$$$ is the number of way to choose $$$p^2$$$ among those $$$k$$$ numbers when you fix squarefree $$$u$$$ (though we are doing in reverse).

The formula

Implementation

O(sqrt n log sqrt n)
O(sqrt log log sqrt n)

Complexity

The complexity of the first implementation is $$$O(\sqrt{n} \log \sqrt{n})$$$

Hint 1
Hint 2
Hint 3
Proof

The complexity of the second implementation is $$$O(\sqrt{n} \log \log \sqrt{n})$$$

Hint 1
Proof





Solution for duplicates elements in array

Extra task C


Idea

It is no hard to proove that we can use the same algorithm as described in task A, B or in original task.

Hint
Proof

Using the same algorithm, the core of calculating is to find out the number of non-decreasing integer sequence of size $$$k$$$ where numbers are in $$$[1, n]$$$.

The formula is

Can you proove it ?

Hint 1
Hint 2
Hint 3
Proof

Now it is done, just that it

The idea is the same as what clyring described here but represented in the other way


Implementation

O(n^3 log n) solution
O(n) solution
O(sqrt n log log sqrt n) solution

Complexity

Well, if you are here then I bet you a discord nitro that you dont need more proofs, lol.






Solution when there are no restriction between k, n, p

Extra task D


Idea

Let just ignore the fact that this need more detail. But as the blog is not about nCk problem I will just make it quick

For prime $$$p$$$ - We can just ignore factors $$$p$$$ in calculating $$$n!$$$. - Then combining it back when calculating for the answer. - If we dont do this $$$n!$$$ become might divides some factors of $$$p$$$.

For squarefree $$$p$$$ - Factorize $$$p = p_1 \times p_2 \times p_q$$$ that all $$$p_i$$$ is prime. - Ignore all factors $$$p_i$$$ when calculate $$$n!$$$. - Remember to calculate how many times factors $$$p_i$$$ appear in $$$1 \dots n$$$. - When query for the answer we just combine all those part back. - Remember you can just take modulo upto $$$\phi(p)$$$ which you can also calculate while factorizing $$$p$$$. - Remember that $$$n!$$$ must not divides any factor $$$p_i$$$ otherwise you will get wrong answer.

For even non square-free $$$p$$$ - Factorize $$$p = p_1^{f_1} \times p_2^{f_2} \times p_q^{f_q}$$$ that all $$$p_i$$$ is unique prime. - We calculate $$$C(n, k)$$$ modulo $$$p_i^{f_i}$$$ for each $$$i = 1 \dots q$$$. - To do that, we need to calculate $$$n!$$$ modulo $$$p_i^{f_i}$$$ which is described here. - To get the final answe we can use CRT. - Yet this is kinda hard to code and debug also easy to make mistake so you must becareful - I will let the implementation for you lovely readers.


Implementation

O(n log mod + sqrt(mod)) for prime p or squarefree p

Complexity

As you might notice $$$p$$$ is atleast prime, or atmost a squarefree number.

Since the complexity also depends on the factors of $$$p$$$, in the worst case, $$$p = 2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17 \times 19 \times \dots$$$ having most factors that is about $$$\log(p)$$$.

Also because of that factorizing and calculating $$$\phi{p}$$$ part take $$$O(\sqrt{p})$$$ time.

So you got $$$O(n \times \log p + \sqrt{p})$$$ in final.

Though you can still optimize this but by doing that why dont you just go straight up to solve for non squarefree $$$p$$$ too ?






Contribution

  • Yurushia for pointing out the linear complexity of squarefree sieve.

  • clyring for fixing typos, and the approach for tasks A, B, C, D, E, G, H, J

Tags combinatorics

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en60 English SPyofcode 2021-11-09 12:21:19 4
en59 English SPyofcode 2021-11-09 12:20:38 6 Tiny change: 'n subimit [https://' -> 'n subimit here: [https://'
en58 English SPyofcode 2021-11-09 12:19:51 265
en57 English SPyofcode 2021-11-09 12:12:22 3178
en56 English SPyofcode 2021-11-05 19:03:46 3619
en55 English SPyofcode 2021-11-01 08:53:10 64
en54 English SPyofcode 2021-11-01 08:43:50 158
en53 English SPyofcode 2021-11-01 06:55:47 2 Tiny change: ' for $k = 3$ in $O(\s' -> ' for $k = 2$ in $O(\s'
en52 English SPyofcode 2021-11-01 06:44:45 71
en51 English SPyofcode 2021-11-01 06:40:09 16954 (published)
en50 English SPyofcode 2021-11-01 06:22:49 49881 (saved to drafts)
en49 English SPyofcode 2021-11-01 05:27:15 49
en48 English SPyofcode 2021-11-01 05:18:00 184
en47 English SPyofcode 2021-10-31 19:17:30 40
en46 English SPyofcode 2021-10-31 19:10:27 5305
en45 English SPyofcode 2021-10-31 12:29:39 196
en44 English SPyofcode 2021-10-31 12:15:21 229
en43 English SPyofcode 2021-10-31 12:12:51 5175
en42 English SPyofcode 2021-10-31 12:04:20 4012 (published)
en41 English SPyofcode 2021-10-31 07:41:25 0 (saved to drafts)
en40 English SPyofcode 2021-10-31 07:10:39 916 Tiny change: ') solution">\n\n```c' -> ') solution for k = 3">\n\n```c'
en39 English SPyofcode 2021-10-31 06:59:31 6996
en38 English SPyofcode 2021-10-30 20:35:28 436
en37 English SPyofcode 2021-10-30 19:51:26 8
en36 English SPyofcode 2021-10-30 19:50:57 168
en35 English SPyofcode 2021-10-30 19:49:17 38
en34 English SPyofcode 2021-10-30 19:48:18 710
en33 English SPyofcode 2021-10-30 19:43:42 6
en32 English SPyofcode 2021-10-30 19:42:58 714
en31 English SPyofcode 2021-10-30 19:36:20 3825
en30 English SPyofcode 2021-10-30 16:20:57 8
en29 English SPyofcode 2021-10-30 16:19:47 2877
en28 English SPyofcode 2021-10-30 16:18:30 56
en27 English SPyofcode 2021-10-30 16:16:24 6543
en26 English SPyofcode 2021-10-30 11:38:14 769
en25 English SPyofcode 2021-10-30 06:48:18 76
en24 English SPyofcode 2021-10-30 06:45:41 23 Reverted to en22
en23 English SPyofcode 2021-10-30 06:41:21 23
en22 English SPyofcode 2021-10-30 05:34:13 2034 Tiny change: ' summary="Hint 2">\n\nThe ' -> ' summary="Proof">\n\nThe '
en21 English SPyofcode 2021-10-30 04:47:01 229
en20 English SPyofcode 2021-10-29 20:05:05 68 Tiny change: '---\n\n## Tasks\n\n' -> '---\n\n## Extra Tasks\n\n'
en19 English SPyofcode 2021-10-29 19:57:01 603
en18 English SPyofcode 2021-10-29 19:50:27 5436 Tiny change: '------\n\n' -> '------\n\n-------------------------\n\n-------------------------\n\n'
en17 English SPyofcode 2021-10-29 17:43:10 26
en16 English SPyofcode 2021-10-29 12:50:12 3892
en15 English SPyofcode 2021-10-29 12:16:06 1739
en14 English SPyofcode 2021-10-29 03:52:02 2
en13 English SPyofcode 2021-10-28 18:40:23 452 Tiny change: '## Statement:\' -> '## The statement:\'
en12 English SPyofcode 2021-10-28 18:31:38 1487
en11 English SPyofcode 2021-10-28 18:09:33 748
en10 English SPyofcode 2021-10-28 13:42:36 278
en9 English SPyofcode 2021-10-28 13:31:37 99
en8 English SPyofcode 2021-10-28 13:23:42 78
en7 English SPyofcode 2021-10-28 13:21:55 1383
en6 English SPyofcode 2021-10-28 13:08:47 885 Tiny change: 'e product effective' -> 'e product $a_i \times a_j \times a_k$ effective'
en5 English SPyofcode 2021-10-28 13:01:32 1 Tiny change: 'n $O\left(sqrt{n} \l' -> 'n $O\left(\sqrt{n} \l'
en4 English SPyofcode 2021-10-28 13:00:39 478
en3 English SPyofcode 2021-10-28 12:53:55 748 (published)
en2 English SPyofcode 2021-10-28 12:42:55 7656
en1 English SPyofcode 2021-10-28 12:05:23 3517 Initial revision (saved to drafts)