SPyofcode's blog

By SPyofcode, history, 11 months 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

  • _SS 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.

  • ta4p 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).

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

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

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

»
11 months ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it

Regarding task G with $$$k=3$$$: It looks like your second implementation is rather close to what I described in my last message. I mentioned then already that it was $$$O(n^{1+\varepsilon})$$$; the reasoning is straightforward. Letting $$$\sigma_0(i)$$$ be the number of divisors of $$$i$$$, the runtime is clearly bounded by $$$\sum_{i=1}^n \sigma_0(i^3)^2$$$, and it's well-known that the divisor-counting function is $$$O(n^\varepsilon)$$$ for any $$$\varepsilon > 0$$$, so that $$$\sum_{i=1}^n \sigma_0(i^3)^2 \leq \sum_{i=1}^n C_{\varepsilon}^6 i^{6 \varepsilon} \in O(n^{1 + 6 \varepsilon})$$$.

I correctly guessed it "may even be $$$\tilde{O}(n)$$$"; the analysis is interesting, but the poly-log factor hidden in the $$$\tilde{O}$$$-notation seems very large. First up: The preprocessing step. Temporarily borrowing your notation, I was able to show precisely that

$$$ \displaystyle \sum_{p=1}^n \left\lfloor\frac{p}{f(p)}\right\rfloor \in \Theta(n \cdot (\log{n})^3). $$$
Proof sketch for upper bound
Proof sketch for lower bound

From this it trivially follows that the main loop takes at least $$$\Omega(n \cdot (\log{n})^6)$$$ time to run. This happens if the $$$\Theta(n \cdot (\log{n})^3)$$$ relevant cube-divisors are reasonably evenly distributed among the $$$n$$$ buckets, but it is quite plausible that this is not the case and the main loop is actually slower. It seems much harder to precisely estimate the complexity of the main loop; the best upper bound I have come up with so far is $$$O(n \cdot (\log{n})^{16})$$$. This comes from applying the same Euler product idea to the multiplicative function $$$i \mapsto \frac{\sigma_0(i^3)^2}{i}$$$, where we have $$$\sum_{i=0}^{\infty} \frac{\sigma_0(p^{3i})^2}{p^i} = 1 + \frac{16}{p} + O(\frac{1}{p^2})$$$, hence the strange 16 exponent. This seems likely to be inefficient for several reasons, not least of which is that applying this direct approach to $$$i \mapsto \frac{\sigma_0(i^3)}{i}$$$ for the preprocess step would give only an $$$O(n \cdot (\log{n})^4)$$$ upper bound, which I already know isn't optimal. Improvement ideas welcome.

EDIT: I am almost sure techniques to estimate this more accurately than I have already exist in the literature. A good first place to look might be the references at oeis:A061502.

  • »
    »
    11 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Amazing work on those analyses. Though the real complexity is still unknown and bounded by $$$O(n \log ^ 4 n)$$$, yet I never expected it to be this fast.

    In the calculation part, we factorize $$$p^3 = a \times b \times c$$$, and we can have 2 optimization options:

    To fix $$$a$$$ then calculate $$$b \times c$$$ but limiting the bound by using binary search or something similar.

    $$$O\left(\overset{n}{\underset{p = 1}{\Large \Sigma}} \underset{a | p^3}{\Large \Sigma} \left(g(a) + \log\left(\frac{p^3}{a}\right)\right) \right)$$$ for $$$g(a)$$$ is the number of satisfied $$$b \times c$$$

    Or to go through the divisor of $$$\frac{p^3}{a}$$$ itself

    $$$O\left(\overset{n}{\underset{p = 1}{\Large \Sigma}} d(a) \times d\left(\frac{p^3}{a}\right) \right)$$$, yet this should be harder to implement without increasing precalculation time by around $$$O(d(n^3))$$$

    It should be somewhat also reduce some amount of $$$O(\log)$$$ factors in calculation part too.

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Optimizing the pre-computation time isn't all that interesting, since the main loop is dominant.

      This paper uses a second-order approximation of $$$\sum_{i=1}^n \frac{f(i)}{i}$$$ for certain multiplicative functions $$$f$$$ and Abel's summation formula to cancel out the largest-order term in my upper bound technique and get a precise estimate on the growth of $$$\sum_{i=1}^n f(i)$$$. Its theorem 1 is directly applicable and shows that $$$\sum_{i=1}^n \sigma_0(i^3) \in \Theta(n \cdot (\log{n})^3)$$$ and $$$\sum_{i=1}^n \sigma_0(i^3)^2 \in \Theta(n \cdot (\log{n})^{15})$$$. The differences between these and the runtimes of the pre-computation loop and main loop respectively come from the [1..n] restriction on factors considered, but this does not gain more than a constant factor. In the former case, this was already shown by my previous comment. For the latter, it is possible to generalize the same idea to pairs of divisors.

      Spoiler

      So, the second implementation is in fact $$$\Theta(n \cdot (\log{n})^{15})$$$. It's obviously possible to lower the number of log factors by a decent amount. Considering just factors of $$$\frac{i}{x}$$$ should get it down to $$$\Theta(n \cdot (\log{n})^9)$$$, since there are 10 ways to partition 3 copies of a prime among 3 factors $$$x$$$, $$$y$$$, $$$z$$$.

      • »
        »
        »
        »
        11 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Can I ask about $$$O(taskG(k=3))$$$, as it seems all other approach are not faster then iterate through factors in a clever way.