SPyofcode's blog

By SPyofcode, history, 3 years ago, In English

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

Since the result can be big, output it under modulo $$$p$$$.

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

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

Problem

Easy Version
Hard Version

Examples

Example 1
Example 2
Example 3

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

Problem

Very Easy Version
Easy Version
Hard Version

Examples

Example 1
Example 2
Example 3

Idea

Definition
The formula

Implementation

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

But while doing research for task H, I found an improvement

O(sqrt (n/k) log log sqrt(n/k) - k) solution

Complexity

The first implementation
The second implementation
The third implementation

Solution for duplicates elements in array

Extra task C

Problem

Given $$$k, n (1 \leq k \leq n \leq 10^9)$$$, count the number of array $$$a[]$$$ of size $$$k$$$ that satisfied

  • $$$1 \leq a_1 \leq a_2 \leq \dots \leq a_k \leq n$$$
  • $$$a_i \times a_j$$$ is perfect square $$$\forall 1 \leq i < j \leq k$$$

Since the result can be big, output it under modulo $$$10^9 + 7$$$.

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

Problem

Given $$$k, n, p (1 \leq k, n, p \leq 10^9)$$$, 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 k$$$

Since the result can be big, output it under modulo $$$p$$$.

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

Problem

Given $$$k, n (1 \leq k \leq n \leq 10^9)$$$, count the number of array $$$a[]$$$ of size $$$k$$$ that satisfied

  • $$$-n \leq a_1 < a_2 < \dots < a_k \leq n$$$
  • $$$a_i \times a_j$$$ is perfect square $$$\forall 1 \leq i < j \leq k$$$

Since the result can be big, output it under modulo $$$10^9 + 7$$$.

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

Problem

Given $$$k, L, R (1 \leq k, L, R \leq 10^9)$$$, count the number of array $$$a[]$$$ of size $$$k$$$ that satisfied

  • $$$L \leq a_1 < a_2 < \dots < a_k \leq R$$$
  • $$$a_i \times a_j$$$ is perfect square $$$\forall 1 \leq i < j \leq k$$$

Since the result can be big, output it under modulo $$$10^9 + 7$$$.

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

Problem

Given $$$k, n (1 \leq k \leq n \leq 10^9)$$$, 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 \times a_t$$$ is perfect cube $$$\forall 1 \leq i < j < t \leq k$$$

Since the result can be big, output it under modulo $$$10^9 + 7$$$.

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

Solution when you are given n and queries for k

Extra task H

Problem

Given $$$n$$$ you have to answer for queries of $$$k$$$ $$$(1 \leq k \leq n \leq 10^9)$$$, count the number of array $$$a[]$$$ of size $$$k$$$ 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 k$$$

Idea

Simplest idea
Observation

Implementation

O(n) precalculate - O(sqrt n - k) query
O(sqrt n) precalculate - O(sqrt (n/k) log log sqrt(n/k) + sqrt n - k) query

Complexity

The first implementation
The second implementation

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

Full text and comments »

  • Vote: I like it
  • +164
  • Vote: I do not like it

By SPyofcode, history, 3 years ago, In English

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

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

Notice that in this blog, we will solve in $$$O(n)$$$ for general $$$k$$$ from the original task

For harder variants you can see in this blog [Variants] An interesting counting problem related to square product

Solution for k = 1

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

Solution for k = 2

Problem

Given $$$n (1 \leq n \leq 10^6)$$$, count the number of pair $$$(a, b)$$$ that satisfied

  • $$$1 \leq a < b \leq n$$$
  • $$$a \times b$$$ is a perfect square.

Since the number can be big, output it under modulo $$$10^9 + 7$$$.

You can submit here: https://lqdoj.edu.vn/problem/aicprtsp2.

Examples

Example 1
Example 2
Example 3

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

Illustration

Squarefree Sieve 10x10 Table | Iteration 0
Squarefree Sieve 10x10 Table | Iteration 1
Squarefree Sieve 10x10 Table | Iteration 2
Squarefree Sieve 10x10 Table | Iteration 3
Squarefree Sieve 10x10 Table | Iteration 5
Squarefree Sieve 10x10 Table | Iteration 6
Squarefree Sieve 10x10 Table | Iteration 7
Squarefree Sieve 10x10 Table | Iteration 10
Squarefree Sieve 10x10 Table | Iteration 11
Squarefree Sieve 10x10 Table | Iteration 13
Squarefree Sieve 10x10 Table | Iteration 14
Squarefree Sieve 10x10 Table | Iteration 15
Squarefree Sieve 10x10 Table | Iteration 17
Squarefree Sieve 10x10 Table | Iteration 19
Squarefree Sieve 10x10 Table | Iteration 21
Squarefree Sieve 10x10 Table | Iteration 22
Squarefree Sieve 10x10 Table | Iteration 23
Squarefree Sieve 10x10 Table | Iteration 100

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

Problem

Given $$$k, n (1 \leq k \leq n \leq 10^6)$$$, 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 k$$$

Since the number can be big, output it under modulo $$$10^9 + 7$$$.

You can submit here: https://lqdoj.edu.vn/problem/aicprtspk.

For $$$k = 3$$$, you can subimit here: https://oj.vnoi.info/problem/dhbb2020_square.

Examples

Example 1
Example 2
Example 3

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

Extra Tasks

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

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

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

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

Full text and comments »

  • Vote: I like it
  • +87
  • Vote: I do not like it