[Variants] An interesting counting problem related to square product

Правка en36, от SPyofcode, 2021-11-05 17:25:43

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

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

Bonus

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
Hint 4
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

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

So.. you might be tired of calculating complexity again and again for those are too familar to you.

So I gonna skip this as the proof is as the same as what you can read above.

But as a bonus, you optimize the problem using this

Then you can solve the problem in $$$O(\sqrt{n} \log \log \sqrt{n} + \sqrt{p} \log^q \ p)$$$ ($$$q$$$ is depended on how you implement it).

Conclusion

For unique array, the complexity is $$$O(\sqrt{n} \log \log \sqrt{n})$$$

For duplicate array, the complexity is $$$O(\sqrt{n} \log \log \sqrt{n} + k)$$$

For duplicate array and small prime $$$p > max(n, k)$$$, the complexity is $$$O(\sqrt{n} \log \log \sqrt{n} + \sqrt{p} \log^q \ p)$$$

Solution when numbers are also bounded by a specific range

Extra task F

Algorithm

We split into 4 cases

The cases

You can easilier solve for each cases in linear

Case 1
Case 2
Case 3
Case 4

Now assumming $$$1 \leq L \leq R$$$, here is how we solve it.

As a simple approach, we can just do like original problem for general $$$k$$$.

We just need to iterative for each fixed squarefree $$$u$$$ and count the number of way to select $$$p^2$$$ as usual but a bit of change.

Why do I get WA

By doing so trivially we can have the complexity of $$$O((R - L + 1) \log R)$$$ time and $$$O(R)$$$ space.

Optimize my time complexity
Hint 1 to optimize space complexity
Hint 2 to optimize space complexity
Hint 3 to optimize space complexity

Is it over ? Cant we do better ?

Isnt there is trivial way that we forget ?
Is there a way that we can iterative through [L, R] ?
Can we have some ways that you iterative not the whole part [1, R] ?
Can we just iterative through [1, \sqrt{R}] and [L, R] to solve it
What is that way ?
Isnt it bad ?
Can we factorize numbers faster ?
Is there another way then pollard rho ?
But how do we count the number of way to select p^2 ?
But how can we iterative for each p^2 ?
Wait is another way to reduce the complexity ?
Wait still we use factorization ?
Another way, but still faster then to apply pollard rho ?
You mean something like sieving or am I wrong in something ?
Isnt the normal sieve we marked for primes, but now the loop is inside, you you mean to...
Can we use the trick like u * c^2 to reduce the number of cases when we take prime as the first loop ?
Wait isnt this a kind of segment sieve ?

So what is that the better solution and how do we implement it steps by steps ?

Solution

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

Well, you might feel bored of long chain of proving for just a simple complexity, now I just make it quick.

Which part you find hard to understand, you can comment below if you cant accept this as an exercise.

For the first implemenetation it is obviously linear time in $$$max(|L|, |R|)$$$ and linear space in $$$|L - R|$$$

For the second implementation it is harder to prove. Yet it is bounded by the complexity of factorizing each number in range $$$[L, R]$$$.

For the third implementation it is based on the fact that:

  • The sum of inversion of prime squared is constant.
  • Each number $$$x$$$ will not be factorized more than $$$O(\log(\sqrt{x}))$$$.
  • You can precalculate binomial coefficient in linear and query for constant time.
  • You can sieve in linear, and only sieve to the square root of $$$R$$$.
  • For each number in the range we care, we just need to visit once.

Yet you can furthur optimize it to $$$O\left(\frac{\sqrt{R} \log \log \sqrt{R}}{\log \sqrt{R}} + \frac{R - L}{\pi^2}\right)$$$.

*I am working on a $$$O {\Large ( } Õ(\sqrt{R}) + Õ(\sqrt{R - L}) {\Large ) }$$$ solution right now as it is much harder to apply the same difficult math idea described in task B.

Solution when the product you must find is a perfect cube

Extra task G

Algorithm

For $$$k < 3$$$, the formula is easy to shown as the second condition always satisfied.

k = 0
k = 1
k = 2

For $$$k > 3$$$, you can prove that every number you selected must share same cubefree therefore just make a cubefree sieve in linear.

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5

But still, you can apply the same idea used in extra task B to achive better complexity.

Instead of throwing a bunch of math using weird formulas with long chain of theorems and proving stuffs.

We can see the algorithm in the other way then come to the formula.

What we had done in task B
What we are going to do in task G

So now we come for the formula:

Defining stuffs
Hint 1
Hint 2
Hint 3
Hint 4
Hint 4
Bonus

Yet in task $$$k = 3$$$ things got differently.

By the theorem used above that if $$$b_x \times b_y$$$ is a cube and $$$b_x, b_y$$$ are cubefree numbers. Then if you know $$$b_x$$$ you can always find one and only one $$$b_y$$$.

Which part you are talking about ????

So instead of a brute-forces, you can fix $$$2$$$ numbers and then you factorize it to the form of cubefree number.

Yet you can know the number of ways to select $$$b_x \times b_y$$$ with precalculation.

Then you can just iterate all over $$$b_z$$$ and count the total of ways to select $$$b_x \times b_y\times b_z$$$.

Since they are ordered, you must becareful, you can update new $$$b_x \times b_y (x < y)$$$ exists whenever your $$$z > y$$$.

Implementation

O(1) || O(n) || O(n^2 log n) solution
O(1) || O(cbrt n) || Õ(n^2) but expected O(n^(0.59)) solution

Complexity

For $$$k < 3$$$, the complexity is obviously $$$O(1)$$$ and we cant optimize further more lol.

For $$$k > 3$$$:

In the first implementation, we use a cubefree sieve in $$$O(n)$$$ and precalculatings for bionomial coefficients is also $$$O(n)$$$.

In the second implementation, we apply the same idea in task B to get the complexity of $$$O(\sqrt[3]{n})$$$

For $$$k = 3$$$:

In the first implementation as you must using factorization, the cost is $$$O(\log n)$$$ for each number, hence you got that complexity.

Bonus
Secondary Bonus
About the actual complexity or better algorithm related to the first the implementation

Yet for the second implementations things gone crazy.

Precalculation part
Calculation part

It has unprovable complexity, though I tried to search for papers, and blogs, even with the help of some GM I find nothing good enough to claim its real complexity.

Yet it might be not the real complexity but also kind of an illusion assumptioning high constant and faking its real higher complexity.

I am making the assumption that the complexity is $$$O(a\times n^b)$$$ for some constant $$$a, b$$$.

Tested for thousands of samples upto $$$n = 10^{8}$$$, using Power Progression Function Algorithm, the power $$$b$$$ seems to be reduced for larger and larger $$$n$$$ as it approach $$$0.5$$$.

Yet for samples upto $$$n = 10^8$$$ it seems to be $$$O(225.014140682692 * x^{0.590337564727864})$$$ but I am not really sure.

Bonus

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.

Теги combinatorics, generalization, mobius, phi, euler totient

История

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