[Tutorial and question] Number of ordered integer set of size k in [1, n] that pairwisely product of perfect square

Правка en6, от SPyofcode, 2021-10-28 13:08:47

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


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


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

Implementation using factorization
Implementation 1
Implementation 2

So about the complexity....

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

Hint 1
Hint 2

For the 2 implementations below, the complexity is linear

Hint 1
Hint 2
Hint 3
Hint 4
Proof

Solve for general k

Using the same logic above, we can easily solve the problem. But we can count with combinatorics

O(n) solution

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:

Swap for loop implementation

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

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

But why do we need these functions.

Well, you see, since $$$(a, b, n)$$$ form a three-term geometric progression then you have $$$b^2 = an$$$

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 as you can easily google, this interesting sequence is A000188

This sequence have 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$$$.
  • bla bla bla

Well, 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.

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

My question

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

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

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

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

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

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

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

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

Теги combinatorics

История

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