Cycles (Розбір)

Solution

First, if we have n = 1 then the answer is simply the array $a$ itself as we cannot do any operations.

Otherwise let g = \gcd(a_1, a_2, \dots, a_n, m) . We will prove that the answer is always [0, 0, 0, \dots, g].

Since every array element is initially divisible by $g$, and $m$ is divisible by $g$, (a_i + a_j) \bmod m is also divisible by $g$. Thus every element in the answer must be a multiple of $g$.

To reach [0, 0, 0, \dots, g] we will use a process similar to the Euclidean algorithm. Realize that adding a_j to a_i m - 1 times is the same as subtracting it once, modulo $m$. Since we can subtract, we can perfectly simulate Euclidean algorithm on one pair and make one element equal to zero and the other to \gcd(a_i, a_j) . Next, we can make the zero element equal to \gcd(a_i, a_j, m) by repeatedly adding \gcd(a_i, a_j) to it.

By taking \gcd(a_i, a_j, m) and pairing it with the next array element and repeating this process for n-1 times, we will be able to make one of the array's elements equal to $g$. Then by repeatedly adding $g$ to any of the other non-zero elements we will be able to make them equal to zero. We are also able to easily move the element equal to $g$ to to the last position and finally achieve [0, 0, 0, \dots, g].

It is impossible to achieve [0, 0, 0, \dots, 0] since the value $g$ is invariant under the operation and this would imply that g = m which is only possible if the array $a$ was equal to [0, 0, 0, \dots, 0] from the start (which is impossible under the constraints).

The final time complexity is \mathcal{O}(n \log m)

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

#define endl "\n"
#define ll long long
#define IOS ios_base::sync_with_stdio(false); cin.tie(nullptr);

int main() {
    IOS;
    int t;
    cin >> t;
    while (t--) {
        int n, m, a;
        cin >> n >> m;
        int g = m;
        for (int i = 0; i < n; i++) {
            cin >> a;
            g = __gcd(a, g);
        }
        if (n == 1) {
            cout << a << endl;
        } else {
            for (int i = 0; i < n - 1; i++) {
                cout << 0 << " ";
            }
            cout << g << endl;
        }
    }

    return 0;
}