Answers to: TUPLES - Editorialhttps://discuss.codechef.com/questions/90271/tuples-editorial<p><a href="https://www.codechef.com/problems/TUPLES">Practice</a> <br>
<a href="https://www.codechef.com/JAN17/problems/TUPLES">Contest</a> </p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/kevinsogo">Kevin Charles Atienza</a> <br>
<strong>Tester:</strong> <a href="https://www.codechef.com/users/iscsi">Istvan Nagy</a><br>
<strong>Editorialist:</strong> <a href="https://www.codechef.com/users/mgch">Misha Chorniy</a></p>
<h1>Difficulty:</h1>
<p>Hard</p>
<h1>Pre-Requisites:</h1>
<p>fft, number theory, inclusion-exclusion</p>
<h1>Problem Statement</h1>
<p>You are given array $X$ consisting $N$ elements. All the elements in the input are integers. 2-dimensional array $Y$ is defined in next way, $Y_{i,j}$ = $X_{i} * X_{j}$ mod $359999$. Find number of integer tuples $a, b, c, d, e, f$, where gcd($Y_{a,b}$, $Y_{c,d}$, $Y_{e,f}$) = 1 modulo $10^9+7$. Denote that $gcd(0, 0) = 0$.
</p><h1>Explanation</h1>
<p>The first part of the solution is using not 2-dimensional array $Y$, instead of that calculate array $Z$ where $Z_{i}$ denotes the frequency of element $i$ in array $Y$, $i$ will be in a range between 0 and 359998. After that problem looks in a next way: we need to find the sum of all $Z_{i} * Z_{j} * Z_{k}$, where $gcd(i, j, k) = 1$.
</p>
<h1>Subtask 1</h1>
<p>$N$ is less or equal than 1000. Let's create array $Y$ in a naive way in $O(N^{2})$. Also, simply calculate array $Z$ in $O(N^{2})$. </p>
<h1>Subtask 2</h1>
<p>A problem of the solution for subtask 1 in a too slow calculation of array $Y$, how to improve it? Let's consider number $359999$ in more detail, $359999 = 599 * 601$, both numbers $599$ and $601$ are primes. What can this fact give to us? Key observation: let we have a prime number $P$, from number theory follows next fact, any prime $P$ has <a href="https://en.wikipedia.org/wiki/Primitive_root_modulo_n">primitive root</a> $G$, in other words:
For every $x$ = $1..P-1$, exists y, such $G^y$ = $x$, $0 <= y < (P-1)$. </p>
<p> Assume that we have the similar problem but with modulo $P$(not 359999), where $P$ is a prime number. Let's find the primitve root for P, call it G. Problem can be divided into two subproblems: where $X_{i}$ is zero or $X_{i}$ isn't zero. Because zero can't be represented using the primitive root of number $P$. $f(X)$ denoting such number that $G^{f(X)} = X$ and $ 0 <= f(X) < (P-1)$ </p>
<p>$Y_{i,j}$ = $X_{i}$ * $X_{j}$ = $G^{f(X_{i})}$*$G^{f(X_{j})}$ = $G^{(f(X_{i}) + f(X_{j}))}$, in case if $X_{i} != 0$ and $X_{j} != 0$.</p>
<p> There are 4 subproblems: </p>
<li> $0 * 0 = 0$ </li>
<li> $0 * B = 0$, $B mod P > 0$ </li>
<li> $A * 0 = 0$, $A mod P > 0$ </li>
<li> $A * B = G^{f(A)} * G^{f(B)} = G^{f(A)+f(B)}$, $A mod P > 0, B mod P > 0$ </li>
<p><code>
zeroes = 0
for i = 1..N
if X[i] % P == 0
zeroes += 1
Z[0] = zeroes * zeroes +
zeroes * (N - zeroes) +
(N - zeroes) * zeroes
for i = 1..N
if X[i] mod P == 0
continue
for j=1..N
if X[j] mod P == 0
continue
da = f(X[i]) // G^da = X[i], 0<=da<(P-1)
db = f(X[j]) // G^db = X[j], 0<=db<(P-1)
dab = da + db // X[i]<em>X[j] = G^(da+db)
Z[(G^dab)%P] += 1
</em></code><em>
</em></p><p><em> How to calculate function $f$ in $O(1)$. Let's make some precomputations, $ff$[$G^i mod P$] = i, for i in the range between $0$ and $P-2$. $f(i)=ff[i]$. Let's rewrite this code a bit, namely precalculate $C_{i}$ - frequency of the number $i$ in the array $X$. </em></p><em>
<code>
for i=1..N
if X[i]%P==0
C[X[i] % P] += 1
else
C[f(X[i])] += 1
Z[0] = C[0] * C[0] + 2 * C[0] * (N - C[0])
for i = 0..P-2
for j = 0..P-2
Z[(G^(i+j))%P] += C[i] * C[j]
</code>
<p> What we see, last code is very similar to multiplication of two polynomials</p>
<code>
for i = 1..N
for j = 1..M
C[i + j] += A[i] * B[j] //Standard multiplication of polynomials
</code>
<p>Try to change the code above a bit</p>
<code>
for i = 0..P-2
for j = 0..P-2
F[i + j] += C[i] * C[j]
for i = 0..2</code></em><code>(P-2)
Z[(G^i)%P] += F[i]
</code>
<p> How to multiplicate two polynomials in way faster than $O(N^2)$, there are many algorithms, let's choose <a href="http://web.cecs.pdx.edu/~maier/cs584/Lectures/lect07b-11-MG.pdf">Fast Fourier Transform</a>. Below pseudocode of multiplication using Fast Fourier Transform. </p>
<code>
D = FFT(C)
for i = 0..2 * (P-2)
E[i] = D[i] * D[i]
F = inverseFFT(E)
for i = 0..2*(P-2)
Z[(G^i)%P] += F[i]
</code>
<p> But we have two primes 599 and 601, what to do in this case? This solution can be modified for the case with two primes, find primitive roots for 599 and 601, let's call them $G$ and $H$. </p>
<p>Now every number between 0 and 359998 can be in one from the four types: </p>
<li> (0, 0), only 0 satisfied this condition </li>
<li> ($G^i mod 599$, 0), only 598 numbers satisfied this condition </li>
<li> (0, $H^i mod 601$), only 600 numbers satisfied this condition </li>
<li> ($G^i mod 599$, $H^j mod 601$) </li><p></p>
<p>How to multiply two numbers from these types, we can multiply first and second components independently from each other. In other words: $(A,B)*(C,D)$=$(A*C mod 599, B*D mod 601)$ from <a href="https://en.wikipedia.org/wiki/Chinese_remainder_theorem"> Chinese Remainder Theorem</a> Consider all possible multiplications from types: </p>
<li> $(0, 0) = (0, 0) * (A, B)$ OR $(A, B) * (0, 0)$, $0 <= A <= 598, 0 <= B <= 600$ </li>
<li> $(0, 0) = (0, A) * (B, 0)$ OR $(C, 0) * (0, D)$, $0 < A, D <= 598, 0 < B, C <= 600$ </li>
<li> $(0, E) = (0, A) * (0, B)$ OR $(0, A) * (C, B)$ OR $(C, A) * (0, B)$, $0 < C <= 598, 0 < A, B, E <= 600$ </li>
<li> $(E, 0) = (A, 0) * (B, 0)$ OR $(A, 0) * (B, C)$ OR $(A, C) * (B, 0)$, $0 < A, B, E <= 598$, $0 < C <= 600$ </li>
<li> $(X, Y) = (A, B) * (C, D)$, $0 < A, C, X <= 598, 0 < B, D, Y <= 600$ </li>
<p> First four convolutions can be processed in time $O(599 * 601) = O(359999)$, consider last convolution(it will be between two multipliers of fourth type): </p>
<p> $(X, Y) = (A, B) * (C, D)$ = $(G^{i1} mod 599, H^{j1} mod 601) * (G^{i2} mod 599, H^{j2} mod 601)$ = $(G^{i1+i2} mod 599, H^{j1+j2} mod 601)$
</p><p> Let's create polynomial $P$, where $P$[$i * 2 * 601 + j$] is the number of numbers $G^{i}*H^{j} mod 359999$, if we'll multiply it by itself with FFT, we can take data of $(X, Y)$</p>
<p> $(i1 * 2 * 601 + j1)$ * $(i2 * 2 * 601 + j2)$ = $(i1 + i2) * 2 * 601 + (j1 + j2)$, $0 <= (j1 + j2) < 2 * 601$ </p>
<p><code>
for i = 0..598
for j = 0..600
P[i * 2 * 601 + j] += A[i][j] // number of numbers which represented in type G^i * H^j % 359999
fft(P)
for i = 0..(1<<21)-1
D[i] = P[i] * P[i] //Multiplying with FFT
Q[i] = inverseFFT(D)
for i = 0..4*359999
i12 = i / (2 * 601)
j12 = i % (2 * 601)
Z[G^(i12)%599 * H^(j12)%601] += Q[i]
</code>
</p><p> After we'll find array $Z$ in fast way. How to speed up the following code: </p>
<code>
ans=0
for i = 0..359999-1
for j = 0..359999-1
for k = 0..359999-1
if gcd(i, j, k) = 1
ans += Z[i] * Z[j] * Z[k]
ans %= 1000 * 1000 * 1000 + 7
</code>
Let's use some inclusion-exclusion, more precisely mobius-function, you can see this tutorial for <a href="https://discuss.codechef.com/questions/46074/coprime3-editorial">similar problem</a>:
But in this problem, we don't need to order $i, j, k$, therefore
<code>
for i = 1..359999
for j = i;j <= 359999; j+=i
D[i] += Z[j];
ans += mu[i] * D[i] * D[i] * D[i] //number of positive integer triplets, where each number is divisible by i multiplied by mobius-function from i
</code>
We forget about zeroes. How to count it:
<li> $i = j = k = 0$, $gcd(i, j, k) = 0$, skip it </li>
<li> $i * j = 0$ OR $j * k = 0$ OR $i * k = 0$, we need to add $Z_{1} * Z_{0} * Z_{0}$ </li>
<li> $i = 0$ OR $j = 0$ OR $k = 0$, we need to find the number of pairs $(a, b)$, where $gcd(Z_{a}, Z_{b}) = 1$ and multiply it by value of $Z_{0}$ </li><p></p>
<p><code>
ans = 3 * Z[1] * Z[0] * Z[0]
for i=1..359999
for j=i;j<=359999; j+=i
D[i]+=Z[j];
ans += mu[i] * D[i] * D[i] * D[i] //number of positive integer triplets, where each number is divisible by i multiplied by mobius-function from i
ans += 3 * mu[i] * D[i] * D[i] //Don't forget about multipling by 3
</code></p>
<p>Overall time complexity of this approach is $O(2^{M} * M + X log X)$, where M = 21, X = 359999.</p>
<h1>Solution:</h1>
<p>Setter's solution can be found <a href="http://www.codechef.com/download/Solutions/JAN17/Setter/TUPLES.cpp">here</a> <br>
Tester's solution can be found <a href="http://www.codechef.com/download/Solutions/JAN17/Tester/TUPLES.cpp">here</a></p>
<p><strong>Please feel free to post comments if anything is not clear to you.</strong></p>enSun, 22 Jan 2017 04:58:08 +0530Answer by kevinsogohttps://discuss.codechef.com/questions/90271/tuples-editorial/90413<p>There's a slight difference in my solution from the one described in this editorial, particularly in the part where you have to count the occurrences of $Y_{i,j}$ coprime to $m = 359999 = 599\cdot 601$. </p>
<p>I'll introduce the notation I'll use. Let $x_v$ be the number of indices $i \in [1, N]$ such that $X_i = v$. Let $y_v$ be the number of index pairs $(i,j) \in [1, N]^2$ such that $Y_{i,j} = v$. Our goal is to compute the values $y_v$ for all $v \in \left(\mathbb{Z}/m\mathbb{Z}\right)^\times$. Here, $\left(\mathbb{Z}/m\mathbb{Z}\right)^\times$ denotes the <strong>multiplicative group of integers mod $m$</strong> and consists of numbers coprime to $m$. This group has $\phi(m)$ elements. </p>
<p>I'll also mention that this explanation requires some standard abstract algebra facts. Nothing too deep, though.</p>
<hr>
<p>If there were a number $g$ that can <strong>generate</strong> all numbers in $\left(\mathbb{Z}/m\mathbb{Z}\right)^\times$, then we can use FFT to compute the $y_v$ by <em>rearranging the elements of $\left(\mathbb{Z}/m\mathbb{Z}\right)^\times$ according to their logarithms base $g$</em>. Specifically, every element of $\left(\mathbb{Z}/m\mathbb{Z}\right)^\times$ is of the form $g^i$ for $i \in [0, \phi(m))$, and we have the equality:</p>
<p>$$ y_{g^i} = \sum_{j=0}^{\phi(m)-1} x_{g^j} \cdot x_{g^{i-j}} $$</p>
<p>for all $i \in [0, \phi(m))$. This is a convolution and can be computed in $O(\phi(m) \log \phi(m))$ time, and the details of this convolution has already been described in the editorial. </p>
<p>But the <strong>generator</strong> $g$ doesn't exist. In fact, it only exists if $m$ is one of the forms $2$, $4$, $p^k$, or $2p^k$, for $k > 0$ and $p$ an odd prime. </p>
<p>Our case $m = 359999 = 599\cdot 601$ isn't of that form. But we can modify the algorithm above to work on our $m$ by using a <em>near generator</em> instead. To explain what I mean by this, note that the most that any number $g$ can generate mod $m = 359999$ is $\phi(m)/2$, or <em>exactly half</em> the numbers. Let's call such a number a <strong>near generator</strong>. An example of a near generator is $g = 7$. This number generates exactly half of the numbers in $\left(\mathbb{Z}/m\mathbb{Z}\right)^\times$. Note that $g^{\phi(m)/2} \equiv 1 \pmod{m}$. </p>
<p>An example of a number that $g = 7$ cannot generate is $17$. Let's define $h = 17$. </p>
<p>Let's denote the set of numbers that $g$ can generate as $(g)$. Notice that: </p>
<ul>
<li>$(g)$ is a <em>subgroup</em> of $\left(\mathbb{Z}/m\mathbb{Z}\right)^\times$, so if we form the cosets of $(g)$, we get two sets: $(g)$ itself and $h\cdot (g)$. This implies that every element of $\left(\mathbb{Z}/m\mathbb{Z}\right)^\times$ is exactly one of the following forms: $g^i$ or $hg^i$, for $i \in [0, \phi(m)/2)$. </li>
<li>$(g)$ is a <em>normal</em> subgroup of $\left(\mathbb{Z}/m\mathbb{Z}\right)^\times$, which means we can form the quotient $\left(\mathbb{Z}/m\mathbb{Z}\right)^\times/(g)$. Furthermore, it must be isomorphic to $\mathbb{Z}/2\mathbb{Z}$, the only group of size 2 (up to isomorphism). This implies that $(h\cdot (g))\cdot (h\cdot (g)) = (g)$. This is the same as saying $h^2 \in (g)$. This is the same as saying $h^2 = g^H$ for some $H \in [0, \phi(m)/2)$. (In fact, $H = 21370$.) </li>
</ul>
<p>Using these facts, we can now compute $y_v$ for various kinds of $v$ using the following: </p>
<p>$$\begin{align*}
y_{hg^i} &= \sum_{j=0}^{\phi(m)/2-1} x_{g^j} \cdot x_{hg^{i-j}} + \sum_{j=0}^{\phi(m)/2-1} x_{hg^j} \cdot x_{g^{i-j}} \\\
y_{g^i} &= \sum_{j=0}^{\phi(m)/2-1} x_{g^j} \cdot x_{g^{i-j}} + \sum_{j=0}^{\phi(m)/2-1} x_{hg^j} \cdot x_{hg^{i-j-H}}
\end{align*}$$</p>
<p>for all $i \in [0, \phi(m)/2)$. Now, we get 4 convolutions which can all be computed with FFT!</p>kevinsogoSun, 22 Jan 2017 04:58:08 +0530https://discuss.codechef.com/questions/90271/tuples-editorial/90413Comment by swetankmodi on mgch's questionhttps://discuss.codechef.com/questions/90271/tuples-editorial#90318<p>A very good problem and editorial! Though i could not solve it during the contest, I can definitely solve it now on my own :D</p>swetankmodiThu, 19 Jan 2017 02:19:34 +0530https://discuss.codechef.com/questions/90271/tuples-editorial#90318Comment by likecs on mgch's questionhttps://discuss.codechef.com/questions/90271/tuples-editorial#90313<p>Very nice Editorial.</p>likecsThu, 19 Jan 2017 00:39:48 +0530https://discuss.codechef.com/questions/90271/tuples-editorial#90313Answer by likecshttps://discuss.codechef.com/questions/90271/tuples-editorial/90296<p>Please upload the full editorial.</p>likecsWed, 18 Jan 2017 18:05:18 +0530https://discuss.codechef.com/questions/90271/tuples-editorial/90296