Magical Palette( The 2024 ICPC Asia Shenyang Regional Contest)
题目描述：体面总结
小白兔有一个魔法调色板，调色板是一个
(
n
×
m
)
(n \times m)
(n×m) 的网格。
在每一行的左边挤出一种颜料
(
a
1
,
a
2
,
…
,
a
n
)
(a_1, a_2, \ldots, a_n)
(a1,a2,…,an)，在每一列的上方挤出一种颜料
(
b
1
,
b
2
,
…
,
b
m
)
(b_1, b_2, \ldots, b_m)
(b1,b2,…,bm)。
在网格的第 (i) 行第 (j) 列的颜色是通过计算公式：
c
i
j
=
(
a
i
⋅
b
j
)
m
o
d
(
n
⋅
m
)
c_{ij} = (a_i \cdot b_j) \mod (n \cdot m) \
cij=(ai⋅bj)mod(n⋅m)
小白兔希望网格中每一个颜色 ( c i j ) (c_{ij}) (cij) 都不相同。
小白兔希望网格中每一个颜色 (c_{ij}) 都不相同。
你的任务是判断是否可能实现，并在可能时输出合适的颜料 ( a 1 , a 2 , … , a n a_1, a_2, \ldots, a_n a1,a2,…,an) 和 ( b 1 , b 2 , … , b m b_1, b_2, \ldots, b_m b1,b2,…,bm)。
首先第一个规律你得搞明白，当两条边gcd不等于1时，你根本就找不到答案！！！
这点非常的重要！！！
当你玩了两幅图后，你可能就有点感觉，比方说：
你可能发现了一点规律，就是有一条边上的数是等差数列，似乎可行，但是当你玩这个样例，仿佛有点毛病
这时，你可以慢慢推理，发现仿佛将长宽上的数都变为等差数列就可行
打表试试没啥问题就好
但是注意一点！！！
当有一条边等于1，或两条边都为1时，特判！！！非常重要
因为题目中有句话叫做
(
0
≤
a
<
n
m
)
(0 \leq a < nm)
(0≤a<nm)
太阴险了
思路分析
-
网格中颜色不同的充要条件：
- 网格中所有颜色 ( c i j c_{ij} cij) 必须覆盖从 (0) 到 ( n ⋅ m − 1 n \cdot m - 1 n⋅m−1) 的所有整数。
- 这需要 ( c i j = ( a i ⋅ b j c_{ij} = (a_i \cdot b_j cij=(ai⋅bj) m o d ( n ⋅ m ) \mod (n \cdot m) mod(n⋅m)) 对 (i) 和 (j) 的所有组合是互异的。
-
关键观察：
- 如果 ( gcd ( n , m ) = 1 \gcd(n, m) = 1 gcd(n,m)=1 )，可以证明通过选择合适的 ( a i a_i ai) 和 ( b j b_j bj)，能确保所有颜色互异。
- 如果 ( gcd ( n , m ) > 1 \gcd(n, m) > 1 gcd(n,m)>1 )，则无法满足要求，因为颜色必然出现重复。
-
构造方法（当 ( gcd ( n , m ) = 1 \gcd(n, m) = 1 gcd(n,m)=1)）：
- 设 ( a i = ( i ⋅ m + 1 a_i = (i \cdot m + 1 ai=(i⋅m+1) m o d ( n ⋅ m ) \mod (n \cdot m) mod(n⋅m))，其中 ( i ∈ [ 1 , n ] i \in [1, n] i∈[1,n])。
- 设 ( b j = ( j ⋅ n + 1 ) m o d ( n ⋅ m ) b_j = (j \cdot n + 1) \mod (n \cdot m) bj=(j⋅n+1)mod(n⋅m))，其中 ( j ∈ [ 1 , m ] j \in [1, m] j∈[1,m])。
- 这样生成的 ( a i a_i ai) 和 ( b j b_j bj) 能保证所有 ( c i j c_{ij} cij) 不同。
-
复杂度分析：
- 构造方法的时间复杂度为 ( O ( n + m ) O(n + m) O(n+m))。
- 对于多个测试用例，总复杂度为 ( O ( T ⋅ ( n + m ) ) O(T \cdot (n + m)) O(T⋅(n+m)))，且输入规模限制保证效率。
代码实现
#include <map>
#include <set>
#include <fstream>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iterator>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdio>
#include <bitset>
#include <iomanip>
#define endl '\n'
#define int long long
#define Max(a, b) (((a) > (b)) ? (a) : (b))
#define Min(a, b) (((a) < (b)) ? (a) : (b))
#define BoBoowen ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;
int n, m;
signed main()
{
int T;
cin >> T;
while (T--)
{
cin >> n >> m;
if (__gcd(n, m) == 1)
{
cout << "Yes" << endl;
for (int i = 1; i <= n; i++)
{
cout << (i * m + 1) % (m * n) << " ";
}
cout << endl;
for (int j = 1; j <= m; j++)
{
cout << (j * n + 1) % (m * n) << " ";
}
cout << endl;
}
else
{
cout << "No" << endl;
}
}
}
详细说明
-
输入输出格式：
- 输入：一个整数 (T)，表示测试用例数。接下来 (T) 行，每行两个整数 (n) 和 (m)。
- 输出：对每个测试用例，输出 “Yes” 和两行数组 (a) 和 (b) 或直接输出 “No”。
-
逻辑说明：
- 使用 (\gcd) 判断是否存在解。
- 如果存在解，利用构造公式生成满足条件的 (a_i) 和 (b_j)。
-
样例解释：
-
样例输入：
2 2 3 2 2 -
样例输出：
Yes 1 2 1 3 5 No -
解释：
- 第一个测试用例中，( gcd ( 2 , 3 ) = 1 \gcd(2, 3) = 1 gcd(2,3)=1)，存在解。通过公式生成 (a = [1, 2])，(b = [1, 3, 5])。
- 第二个测试用例中，( gcd ( 2 , 2 ) = 2 > 1 \gcd(2, 2) = 2 > 1 gcd(2,2)=2>1)，无解。
-
复杂度评估
- 每次构造 (a) 和 (b) 的复杂度为 ( O ( n + m ) O(n + m) O(n+m))。
- 总复杂度为 ( O ( sum of all ( n + m ) ) ≤ 1 0 6 O(\text{sum of all } (n + m)) \leq 10^6 O(sum of all (n+m))≤106)，能够在时间限制内运行。
总结
- 通过 (\gcd) 快速判断是否存在解。
- 利用简单的线性公式构造满足条件的解。
- 算法高效且易于实现，适合大规模输入场景。