1295D - Same GCDs

Link to the problem : https://codeforces.com/problemset/problem/1295/D

I had to see the tutorial to understand this.

$$ gcd(a, m) = gcd(a + x, m)$$

Now, using Euclid's algorithm, we can say that 

$$ gcd(a, b) = gcd(a - b, b)$$

So, in our case, that would be:

$$ gcd(a + x, m) = gcd(a + x - m, m) = gcd(a + x - 2 \times m, m) = ...  = gcd((a + x) \% m, m)$$

Now, in the problem it's given that $ 0 \leq x < m$, so we can say that $ a \leq a + x < a + m$, and therefore we can also say that $ 0 \leq (a + x)\%m < m$

So, we can assume $$ Y = (a + x)\%m $$

We can say:

$$ gcd(a, m) = gcd(a + x, m) = gcd(Y, m)$$

Let's say that $gcd(a, m) = G$

So $$ gcd(Y, m) =  G$$

This means that G can divide both Y, and m, and there are no further common divisors (besides 1) in Y and m. This means:

$$ gcd(Y / G, m / G) = 1$$

Now notice that the variable here is $Y/G$. We want it to be such that it's co-prime to $m/G$. Also notice that since $Y < m$, $Y/G < m/G$. Therefore the Euler's totient function is applicable here. More details on that : https://cp-algorithms.com/algebra/phi-function.html

So we just need to calculate the totient function for $m/G = m / gcd(a, m)$

My submission : https://codeforces.com/contest/1295/submission/240298664

1462E2 - Close tuples

#codeforces

Link : https://codeforces.com/problemset/problem/1462/E2

The crux here is to see that we only need to see elements for \(x+k\) where \(x\) is the minimum element in the tuple, and \(x+k\) is the maximum element in the tuple.

So we can leave the notion of the ordered elements inside the array, and keep track of magnitudes.

We can create a map, from the item value to it’s count. So an array like : 1 1 2 2 3 4 5, will create a map:

\[ 1 \rightarrow 2 \] \[ 2 \rightarrow 2 \] \[ 3 \rightarrow 1 \] \[ 4 \rightarrow 1 \] \[ 5 \rightarrow 1 \]

Next, we do a prefix sum. So the map will look like:

\[ 1 \rightarrow 2 \] \[ 2 \rightarrow 4 \] \[ 3 \rightarrow 5 \] \[ 4 \rightarrow 6 \] \[ 5 \rightarrow 7 \]

Here, let’s think we are at the first element 1. And if \(k = 2\), then \(1 + k = 3\), so we see how many elements there are until 3 => 5. This already includes the “1” we are looking at, so we should reduce this by 1, to 4.

Since we have decided that the minimum element will be 1, so we only need to worry about the remaining \(m-1\) elements. So we do a combination here, and say \(^4C_{m-1}\) here. Why? Because all maximum elements until 3 work just fine. Even if we have 2 as the largest element, it still would suffice the condition inside the problem.

Now some details: What about the second 1? So when we calculated the tuples for the first 1, we took the cases when the second one is also taken. So when we are calculating for the 2nd one, we should not take the first one into account.

Therefore, the total elements for calculation would become \(4-1 = 3\), and it’s combinations would be : \(^3C_{m-1}\) - This we need to keep decreasing for all the duplicates.

Note that since we are doing MODs in the end, the combinations can also be simplified by doing MODs. MOD of the denominator of the combination would be done via inverse modulus.

My submission : https://codeforces.com/contest/1462/submission/221887357