[Tutorial] An interesting counting problem related to square product

Revision en43, by SPyofcode, 2021-10-31 12:12:51

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

Solved 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) solution
O(sqrt n log sqrt n + k) solution
O(sqrt n log log sqrt n + k) solution

Complexity

In the first implementation it is obviously linear.

Hint 1
Hint 2

The second and third implementation is also easy to show its complexity

Hint 1
Hint 2

Sadly, since $$$k \leq n$$$. We also conclude that the complexity is $$$O(n)$$$, and even worse it also contains large constant factor compared to that in the first implementation.

But it is still effecient enough to solve problem where $$$k$$$ is small.






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

Extra task D


Idea

So first of all, the result do depend on how you calculate binomial coefficient but they are calculated independently even if you can somehow manage to use the for loop of binomial coeffient go first.

Therefore even if there is no restriction between $$$k, n, p$$$, the counting part and the algorithm doesnt change.

You just need to change how you calculate binomial coefficient, and that is all for this task.

Let just ignore the fact that though this need more detail, but as the blog is not about nck problem I will just make it quick

For large prime $$$p > max(n, k)$$$

  • Just using normal combinatorics related to factorial (since $$$p > max(n, k)$$$ nothing will affect the result)
  • For taking divides under modulo you can just take modular inversion (as a prime always exist such number)
  • Yet this is standard problem, just becareful of the overflow part
  • You can also optimize by precalculating factorial, inversion number and inversion factorial in linear too

For general prime $$$p$$$

  • We can just ignore factors $$$p$$$ in calculating $$$n!$$$.
  • You also need to know how many times factor $$$p$$$ appears in $$$1 \dots n$$$
  • Then combining it back when calculating for the answer.
  • If we dont do this $$$n!$$$ become might divides some factors of $$$p$$$.
  • By precalculation you can answer queries in $$$O(1)$$$

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.
  • By precalculation you can answer queries in $$$O(\log p)$$$

For general positive modulo $$$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 answer 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.
  • Yet depends on how you calculate stuffs that might increase your query complexity
  • There are few (effective or atleast fully correct) papers about this but you can read the one written here

Implementation

O(n) for prime p > max(n, k)
O(n log mod + sqrt(mod)) for prime p or squarefree p

Complexity

In the first implementation it is obviously linear.

Hint

And for the second implementation.

Hint 1
Hint 2

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

Bonus

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






Solution when numbers are also bounded by negative number

Extra task E


Idea

Yet this is the same as extra task C where only the counting part should be changed.

As we only care about integer therefore let not use complex math into this problem.

If there exist a negative number and a positive number, the product will be negative thus the sequence will not satisfied.

Becareful, there are the zeros too.

When the numbers are all unique, or $$$-n \leq a_1 < a_2 < \dots < a_k \leq n$$$

There are 4 cases:

Thus give us the formula of $$$task_E(n, k) = 2 \times task_B(n, k) + 2 \times task_B(n, k - 1)$$$.

Hint 1
Hint 2
Hint 3
Proof

Remember that when $$$k = 0$$$ the answer is $$$0$$$ otherwise you might somewhat having wrong result for negative number in binomial coefficients formula


So what if I mix the problem with task C too ?

When the numbers can have duplicates, or $$$-n \leq a_1 \leq a_2 \leq \dots \leq a_k \leq n$$$

There are 5 cases:

Yet once again you can simplified it with less cases for easier calculation.

There are 2 main cases:

Thus give us the formula of $$$task_E(n, k) = 1 + 2 \times \overset{k}{\underset{t = 1}{\Large \Sigma}} task_B(n, t)$$$.

Why the formula is 2 * ...?
No I mean why there is no binomial coefficients for selecting the number of zeros ?
So where is the part 1 come frome ? - Why isnt it 2 instead ?

But this give you a $$$O(k)$$$ solution.

You can do better with math

Hint 1
Hint 2
Solution

Implementation

O(sqrt n log log sqrt n) when the numbers are unique
O(kn) = O(n^2) when duplicates are allowed
O(k sqrt n log sqrt n) = O(n sqrt n log n) when duplicates are allowed
O(k sqrt n log log sqrt n) = O(n sqrt n log log n) when duplicates are allowed
O(k sqrt n + sqrt n log log sqrt n) = O(n sqrt n) when duplicates are allowed
O(k + sqrt n log log sqrt n) = O(n) when duplicates are allowed





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)