NOIP2025模拟赛19 C. 调色板【NOIP2025模拟赛T3】证明

· · 个人记录

我们用严格的数学语言证明代码的正确性：

1. 解的存在性条件

定理：存在数组 a \in [0, nm)^n 和 b \in [0, nm)^m 使得所有 c_{i,j} = (a_i \cdot b_j) \bmod (nm) 互不相同，当且仅当 \gcd(n, m) = 1。

必要性

假设存在合法解， \gcd(n, m) = d > 1。
令 n = d \cdot n',\ m = d \cdot m'，则 nm = d^2 n' m'。
对任意 a_i, b_j，有：

a_i \cdot b_j \equiv (a_i \bmod d) \cdot (b_j \bmod d) \bmod d

由于 a_i \bmod d \in \{0, 1, ..., d-1\} 且 b_j \bmod d \in \{0, 1, ..., d-1\}，乘积模 d 最多有 d^2 种可能。
但需要覆盖 nm = d^2 n' m' 个不同值，根据抽屉原理，必存在 c_{i,j} = c_{i',j'}，矛盾。故 \gcd(n, m) = 1。

下证此构造满足所有 c_{i,j} 互不相同。

2. 构造方法的有效性

目标：按照

\begin{align*} a_i &= (i \cdot m + m - 1) \bmod (nm) \quad (1 \leq i \leq n) \\ b_j &= (j \cdot n + n - 1) \bmod (nm) \quad (1 \leq j \leq m) \\ c_{i,j} &= (a_i \cdot b_j) \bmod (nm) \end{align*}

的方式进行构造，证明若 c_{i_1,j_1} = c_{i_2,j_2}，则 i_1 = i_2 且 j_1 = j_2。

中国剩余定理（CRT)

因 \gcd(n, m) = 1，故：

x \equiv y \bmod (nm) \iff x \equiv y \bmod n \text{且} x \equiv y \bmod m

1：证明 i_1 = i_2

由 c_{i_1,j_1} = c_{i_2,j_2}，结合 CRT 得：

(a_{i_1} \cdot b_{j_1}) \equiv (a_{i_2} \cdot b_{j_2}) \bmod n \tag{1}

计算 b_j \bmod n：

b_j = j \cdot n + (n-1) \implies b_j \equiv -1 \bmod n

代入式 (1)：

a_{i_1} \cdot (-1) \equiv a_{i_2} \cdot (-1) \bmod n \implies a_{i_1} \equiv a_{i_2} \bmod n

计算 a_i \bmod n：

a_i = i \cdot m + (m-1) \implies a_i \equiv m \cdot i + (m-1) \bmod n

故：

m \cdot i_1 + (m-1) \equiv m \cdot i_2 + (m-1) \bmod n \implies m(i_1 - i_2) \equiv 0 \bmod n

因 \gcd(n, m) = 1，故 i_1 \equiv i_2 \bmod n。又 i_1, i_2 \in [1, n]，得 i_1 = i_2。

2：证明 j_1 = j_2

同理，由 c_{i_1,j_1} = c_{i_1,j_2}，结合 CRT 得：

(a_{i_1} \cdot b_{j_1}) \equiv (a_{i_1} \cdot b_{j_2}) \bmod m \tag{2}

计算 a_i \bmod m：

a_i = i \cdot m + (m-1) \implies a_i \equiv -1 \bmod m

代入式 (2)：

(-1) \cdot b_{j_1} \equiv (-1) \cdot b_{j_2} \bmod m \implies b_{j_1} \equiv b_{j_2} \bmod m

计算 b_j \bmod m：

b_j = j \cdot n + (n-1) \implies b_j \equiv n \cdot j + (n-1) \bmod m

故：

n \cdot j_1 + (n-1) \equiv n \cdot j_2 + (n-1) \bmod m \implies n(j_1 - j_2) \equiv 0 \bmod m

因 \gcd(n, m) = 1，故 j_1 \equiv j_2 \bmod m。又 j_1, j_2 \in [1, m]，得 j_1 = j_2。

结论

所以

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

long long gcd(long long  a,long long b) { return b==0?a:gcd(b,a%b); }
long long lcm(long long a,long long b) { return a/gcd(a,b)*b; }

void solve()
{
    cin>>n>>m;
    if(gcd(n,m)!=1)
    {
        cout<<"No"<<endl;
        return;
    }
    cout<<"Yes"<<endl;
    for(int i=1;i<=n;i++) cout<<(i*m+(m-1))%(n*m)<<" ";
    cout<<endl;
    for(int i=1;i<=m;i++) cout<<(i*n+(n-1))%(n*m)<<" ";
    cout<<endl;
}

signed main()
{
    int TT; for(cin>>TT;TT;TT--) 
    solve();
    return 0;
}

代码完全正确。