[Variants] An interesting counting problem related to square product

Revision en48, by SPyofcode, 2021-11-07 12:45:40

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.

Notice that in this blog, we will solve for generalized harder variants

For original problem you can see in this blog [Tutorial] An interesting counting problem related to square product


Extra Tasks

These are harder variants, and generalization from the original problem. You can see more detail here

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

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

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

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

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

Solved 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 also solve the problem where there are no order: Just simply $$$0 \leq a_i \leq n$$$ ?

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

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

O: What if the condition is just two nearby elements and not all pairs. Or you can say $$$a_i \times a_{i+1} \forall 1 \leq i < n$$$ is a perfect square ?

A better solution for k = 2

Extra task A

Idea

Observation
Definition
Property
Formula

Implementation

O(sqrt n log log sqrt n) solution
O(sqrt) solution
Complexity
Hint

A better solution for general k

Extra task B

Idea

Definition
The formula

Implementation

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

Complexity

The first implementation
The second implementation

Solution for duplicates elements in array

Extra task C

Idea

Observation
Calculation

Implementation

O(n) solution
O(sqrt n log sqrt n + k) solution
O(sqrt n log log sqrt n + k) solution

Complexity

The first implementation
The second and third implementation

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

Extra task D

Idea

Observation
Large prime p

Implementation

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

Complexity

Spoiler

Solution when numbers are also bounded by negative number

Extra task E

Idea

Hint
With duplicates case

Implementation

O(sqrt n log log sqrt n) when the numbers are unique

And for duplicates (mixed with task C), we have:

O(kn) = O(n^2)
O(k sqrt n log sqrt n) = O(n sqrt n log n)
O(k sqrt n log log sqrt n) = O(n sqrt n log log n)
O(k sqrt n + sqrt n log log sqrt n) = O(n sqrt n)
O(k + sqrt n log log sqrt n) = O(n)

Complexity

Spoiler

Conclusion

Spoiler

Solution when numbers are also bounded by a specific range

Extra task F

Idea

Observation
Optimization

Implementation

Let $$$Z = max(|L|, |R|)$$$

O(Z) time - O(R - L) space
O(R * sqrt(Z) / log(Z)) time - O(R - L) space
O(sqrt R log log R + (R - L)) time - O(R - L) space

Complexity

Spoiler

Solution when the product you must find is a perfect cube

Extra task G

Idea

k < 3
k > 3
k = 3

Implementation

k<3::O(1) || k>3::O(n) || k=3::O(n^2 log n) solution
k<3::O(1) || k>3::O(cbrt n log cbrt n) || k=3::Õ(n) but practically O(n^(0.59)) for small n
k<3::O(1) || k>3::O(cbrt n log log cbrt n) || k=3::Õ(n) but practically fast

Complexity

k < 3
k > 3
k = 3

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.

  • errorgorn for adding details, and the approach for task F, J, M, O, better complexity for C, E, G.

  • cuom1999 for participating $$$O(n^2)$$$ approach for problem G.

  • vinfat for participating approach related to factorize $$$p^3$$$ into $$$3$$$ product partions in problem G though failed to achive better complexity (editted: confirmed that the complexity seems to be better now).

  • Lihwy, jalsol for combinatorics calculation and the proof of stars and bars in task C.

  • Editorial Slayers Team Lyde DeMen100ns Duy_e OnionEgg QuangBuiCPP _FireGhost_ Shironi for reviewing, fixing typos and feed backs.

Tags combinatorics, generalization, mobius, phi, euler totient

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en58 English SPyofcode 2022-08-11 06:44:58 1 Fixing Latex Notation
en57 English SPyofcode 2022-08-11 06:43:05 47
en56 English SPyofcode 2022-08-11 06:40:20 80 Fix latex notations.
en55 English SPyofcode 2021-11-10 19:53:18 1215
en54 English SPyofcode 2021-11-09 16:59:56 533
en53 English SPyofcode 2021-11-09 12:12:28 1853 Tiny change: '^9 + 7$.\nFor $n \' -> '^9 + 7$.\n\nFor $n \'
en52 English SPyofcode 2021-11-08 13:43:39 1194
en51 English SPyofcode 2021-11-08 06:13:01 13
en50 English SPyofcode 2021-11-07 16:25:16 6097 Tiny change: 'es of $k$ (1 \leq k ' -> 'es of $k$ $(1 \leq k '
en49 English SPyofcode 2021-11-07 14:18:44 12
en48 English SPyofcode 2021-11-07 12:45:40 155 Reverted to en46
en47 English SPyofcode 2021-11-07 12:28:35 155
en46 English SPyofcode 2021-11-06 16:50:00 285 Tiny change: 't \rfloor \right + \unders' -> 't \rfloor + \unders'
en45 English SPyofcode 2021-11-06 14:33:23 12
en44 English SPyofcode 2021-11-06 13:46:02 153
en43 English SPyofcode 2021-11-06 07:13:11 57
en42 English SPyofcode 2021-11-06 07:06:43 3009
en41 English SPyofcode 2021-11-06 04:59:50 35
en40 English SPyofcode 2021-11-06 04:11:51 7
en39 English SPyofcode 2021-11-06 04:11:11 556
en38 English SPyofcode 2021-11-06 03:56:31 933
en37 English SPyofcode 2021-11-06 02:55:34 920 Tiny change: '*\n\n#### Algorithm\n\n<spoil' -> '*\n\n#### Idea\n\n<spoil'
en36 English SPyofcode 2021-11-05 17:25:43 37 Tiny change: 'squarefree as **it j' -> 'squarefree, it is not how we use in the formula as **it j'
en35 English SPyofcode 2021-11-05 17:11:33 8990
en34 English SPyofcode 2021-11-05 17:03:34 14732
en33 English SPyofcode 2021-11-05 16:50:02 4141
en32 English SPyofcode 2021-11-05 10:36:09 617
en31 English SPyofcode 2021-11-05 07:21:43 631
en30 English SPyofcode 2021-11-05 06:45:33 246
en29 English SPyofcode 2021-11-05 06:39:36 2084
en28 English SPyofcode 2021-11-03 05:22:22 537
en27 English SPyofcode 2021-11-03 05:04:31 1713
en26 English SPyofcode 2021-11-03 03:04:41 58
en25 English SPyofcode 2021-11-02 19:52:48 5 Tiny change: 'log/entry/edit/96379)**\' -> 'log/entry/96379)**\'
en24 English SPyofcode 2021-11-02 13:30:46 44
en23 English SPyofcode 2021-11-02 12:45:42 90
en22 English SPyofcode 2021-11-02 12:43:07 181
en21 English SPyofcode 2021-11-02 12:30:16 107
en20 English SPyofcode 2021-11-02 12:28:56 50
en19 English SPyofcode 2021-11-02 12:27:13 5785
en18 English SPyofcode 2021-11-02 04:29:23 46 Tiny change: 'g,2021-7-11] for fixi' -> 'g,2021-7-12] for fixi'
en17 English SPyofcode 2021-11-01 20:05:24 74
en16 English SPyofcode 2021-11-01 14:07:51 12
en15 English SPyofcode 2021-11-01 13:56:28 7 Tiny change: ' generalization harder va' -> ' generalized harder va'
en14 English SPyofcode 2021-11-01 13:50:48 92
en13 English SPyofcode 2021-11-01 13:35:43 24 Tiny change: 'qrt{R - L} {\Large )' -> 'qrt{R - L}) {\Large )'
en12 English SPyofcode 2021-11-01 13:33:59 299
en11 English SPyofcode 2021-11-01 13:31:23 188
en10 English SPyofcode 2021-11-01 13:27:51 9686 Tiny change: 'ask **F, J**, better' -> 'ask **F, J, M, O**, better'
en9 English SPyofcode 2021-11-01 08:44:03 156
en8 English SPyofcode 2021-11-01 06:59:09 39
en7 English SPyofcode 2021-11-01 06:51:52 29
en6 English SPyofcode 2021-11-01 06:50:49 77
en5 English SPyofcode 2021-11-01 06:49:01 21
en4 English SPyofcode 2021-11-01 06:44:37 71
en3 English SPyofcode 2021-11-01 06:42:35 605
en2 English SPyofcode 2021-11-01 06:40:17 15718 (published)
en1 English SPyofcode 2021-11-01 06:22:35 32737 Initial revision (saved to drafts)