The Balance of the Universe

Author : Udynamo

Required Knowledge : String Modulo, Modulo Arithmetic

Time Complexity : $\mathcal{O}(|N| + D)$

Editorialist : Udynamo

Approach:

First, let's understand our goal, which is to make $N$ divisible by $D$. To achieve this, we can perform one operation any number of times: add $M$ to $N$. This gives us a clear mathematical goal: find the smallest non-negative integer $x$ that satisfies the equation:

$(N + M \cdot x) \% D = 0$

The first thing to notice is that $N$ is a huge number given as a string, so we can't store it in a standard long long. Let's simplify our equation using a key property of modular arithmetic:

$(A + B) \% D = ((A \% D) + (B \% D)) \% D$

Applying this to our goal equation, we get:

$(N + M \cdot x) \% D = ((N \% D) + (M \cdot x) \% D) \% D$

This shows that we don't need the entire number $N$. We only need its remainder when divided by $D$, which we'll call $rem$.

So, our new, simpler goal is to find the smallest $x$ such that: $(rem + (M \cdot x) \% D) \% D = 0$

Since we can't calculate $N \% D$ directly, we will calculate it using string modulo by processing the string $N$ digit by digit. We initialize $rem = 0$, and for each digit c in the string, we update $rem = (rem \cdot 10 + (c - \text{'0'})) \% D$. After looping through all the digits, the final value of $rem$ is exactly $N \% D$.

With the remainder $rem$ calculated, we just need to test values of $x$ starting from $0$ to $D - 1$. Why check only from $0$ to $D-1?$ We only need to check $x$ from $0$ to $D-1$ because the sequence of remainders, $(rem + M \cdot x) \% D$, is periodic and must repeat every $D$ steps.

Consider the remainder at step $x$ and step $x+D$:

Remainder at $x$: $R_x = (rem + M \cdot x) \% D$

Remainder at $x+D$: $R_{x+D} = (rem + M \cdot (x+D)) \% D$

Let's expand the second one: $R_{x+D} = (rem + M \cdot x + M \cdot D) \% D$

Since $(M \cdot D) \% D$ is always $0$, this simplifies to:

$R_{x+D} = ((rem + M \cdot x) \% D + 0) \% D = R_x$

This proves the remainder at step $x+D$ is identical to the one at step $x$. The pattern of remainders from $x=0$ to $D-1$ will simply repeat.

We loop with $x$ from $0$ to $D-1$. The first value of $x$ that satisfies our equation, $(rem + (M \cdot x) \% D) \% D = 0$, is the smallest one, and that is our answer. If we finish the entire loop (from $0$ to $D-1$) and no $x$ satisfies the equation, it means a solution is impossible (because the pattern just repeats). In this case, we output $-1$.

Setter's Code:

// Author : Udynamo

#include <bits/stdc++.h>
#define int long long
using namespace std;

const bool test_cases = true;
const int mod = 1e9 + 7, INF = 1e18;

void UNsolve() {
    
    string N;
    cin >> N;
    int M, D;
    cin >> M >> D;

    //String Modulo
    int rem = 0;
    for(int i = 0; i < N.size(); i++){
        rem = rem * 10 + (N[i] - '0');
        rem %= D;
    }

    for(int i = 0; i < D; i++){
        if((rem + (M * i) % D) % D == 0){
            cout << i << endl;
            return;
        }
    }

    //impossible case
    cout << -1 << endl;
}

signed main() {

    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    if (test_cases) cin >> t;
    while (t--) {
        UNsolve();
    }
    return 0;
}

Tester's Code:

def solve():
    n, m, d = input().split()
    m = int(m)
    d = int(d)

    r = 0
    for c in n:
        r = (r * 10 + (ord(c) - ord('0'))) % d

    for i in range(d + 1):
        if (r + m * i) % d == 0:
            print(i)
            return

    print(-1)


t = int(input())
for _ in range(t):
    solve()