D - Marking Editorial by en_translator
In order to solve this problem, you need to know (or figure out by experiments etc.) the following fact:
Let \(A\) and \(B\) be positive integers, and \(g\) be the greatest common divisor of \(A\) and \(B\). Let \(A=ag\) and \(B=bg\); then \(a\) integers \(0,B \bmod A,2B \bmod A,\dots,(a-1)B\bmod A\) contain each of \(0,g,2g,\dots,(a-1)g\) (that is, all multiples of \(g\) between \(0\) and \(A-1\), inclusive) exactly once.
Proof
Since $A$ and $B$ are both multiples of $g$, an integer obtained by adding and subtracting $A$ and $B$ is also a multiple of $g$. Since "the remainder by $A$" is obtained by "adding or subtracting $A$ until it fits within $0$ and $A-1$," all of $0,B \bmod A,2B \bmod A,\dots,(a-1)B\bmod A$ are multiples of $g$. Thus, all that left is to show that $0,B \bmod A,2B \bmod A,\dots,(a-1)B\bmod A$ are distinct. Suppose that there are $i$ and $j$ $(0\leq i < j < a)$ such that $iB \bmod A = jB \bmod A$. Then $jB-iB=(j-i)gb$ is a multiple of $A=ga$; since $a$ and $b$ are coprime, $(j-i)$ is a multiple of $a$. This contradicts with $i,j\ (0\leq i < j < a)$, so the original conjecture is proven.
For example, if \(A=12,B=9\), where \(g=3,a=4,b=3\), then \(0,B\bmod A,2B\bmod A, 3B\bmod A\) are \(0,9,6,3\), respectively, where all multiples of \(g\) between \(0\) and \(A\) occurs once each.
How can we use this fact to solve the original problem? First of all, let \(g\) be the greatest common divisor of \(N\) and \(g\), and let \(N=gn\) and \(D=gd\).
Since \(0,D \bmod N,2D \bmod N,\dots,(n-1)D\bmod N\) are distinct, the \(i\)-th \((1\leq i \leq n)\) square to be marked is \((i-1)D\bmod N\).
When \(n <N\), i.e. \(g\geq2\), which is the \((n+1)\)-th square to be marked? Initially, \(x\) is initialized with \(nD\bmod N\), but \(nD = gnd=Nd\), so \(x=0\), which is marked already. That’s why we set \(x=1\); since square \(1\) is not marked yet because \(g\geq2\), square \(1\) is the \((n+1)\)-th square to be marked. Later on, squares \(1,1+(D \bmod N),1+(2D \bmod N),\dots,1+((n-1)D\bmod N)\) are marked, just as before; then \(x\) is initialized with \(x=1\), which is updated to \(x=2\), … and so on. To roll up, the operations proceed as follows:
- The \(i\)-th \((1\leq i \leq n)\) square to be marked is \((i-1)D\bmod N\), so all squares that are multiples of \(g\) are marked.
- The \((n+i)\)-th \((1\leq i \leq n)\) square to be marked is \(1+((i-1)D\bmod N)\), so all squares whose remainders by \(g\) are \(1\) are marked.
- The \((2n+i)\)-th \((1\leq i \leq n)\) square to be marked is \(2+((i-1)D\bmod N)\), so all squares whose remainders by \(g\) are \(1\) are marked.
- (And so on)
Therefore, the \(K\)-th square to be marked appears to be \(\lfloor \frac{K-1}{n} \rfloor + ((K-1)D \bmod N)\).
Writer’s solution (C++):
#include<bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n, d, k;
cin >> n >> d >> k;
--k;
int a = n / gcd(n, d);
cout << (long long) d * k % n + k / a << '\n';
}
}
posted:
last update: