Codeforces 1266C Diverse Matrix 题解

发表于 | 更新于 | 阅读次数：
本文字数： 641 字 | 阅读时长 ≈ 3 分钟

题意简述

构造一个r行c列的矩阵，r,c<=500，满足：
不存在1<=i<=r，1<=j<=c，使得第i行所有数的gcd=第j列所有数的gcd（即：行，列gcd两两不同）多解输出任意一个。无解输出0。

思路框架

  1. 只有1x1的矩阵是无解的
  2. r=1的情况，显然只要令矩阵为[2,3,4…c+1]即珂。c=1同理。
  3. 别的情况，令第$i$行的$gcd$为$i$，第$i$列的$gcd$为$r+i$即珂。这样行，列的$gcd$正好是$1,2,3…r+c$，完美而潇洒。

具体思路

思考一个问题：如何令第$i$行的$gcd$为$i$，第$i$列的$gcd$位$r+i$？

那很简单，拿行举例：第$i$行的$gcd$为$i$，那就让每个数都是i乘上一个东西即珂。乘上的东西要互质。

如何保证互质呢？我们发现，此时$r,c>=2$，而连续的两个（或以上）个正整数之间，$gcd$肯定是$1$。所以我们只要让第$i$行为$c$个连续正整数即珂。列同理。

稍加思索，我们令第$i$行第$j$列为：$i*(j+r)$。这样，对于任意的$i$，第$i$行所有数都是$i$乘上$c$个连续的正整数；对于任意的$i$，第$I$列所有数都是$i$乘上$r$个连续的正整数。满足条件。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet
{
    #define N 1333
    #define F(i,l,r) for(int i=l;i<=r;++i)
    #define D(i,r,l) for(int i=r;i>=l;--i)
    #define Fs(i,l,r,c) for(int i=l;i<=r;c)
    #define Ds(i,r,l,c) for(int i=r;i>=l;c)
    #define MEM(x,a) memset(x,a,sizeof(x))
    #define FK(x) MEM(x,0)
    #define Tra(i,u) for(int i=G.Start(u),__v=G.To(i);~i;i=G.Next(i),__v=G.To(i))
    #define p_b push_back
    #define sz(a) ((int)a.size())
    #define iter(a,p) (a.begin()+p)

    void R1(int &x)
    {
        x=0;char c=getchar();int f=1;
        while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar();
        while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
        x=(f==1)?x:-x;
    }
    int a[N][N];
    int r,c;
    void Input()
    {
        R1(r),R1(c);
    }
    void Soviet()
    {
        if (r==1 and c==1) {return (void)puts("0");}
        if (r==1) {F(i,1,c) printf("%d ",i+1);return;}
        if (c==1) {F(i,1,r) printf("%d ",i+1);return;}

        F(i,1,r) F(j,1,c) a[i][j]=i*(j+r);
        F(i,1,r) F(j,1,c) printf("%d%c",a[i][j]," \n"[j==c]);

    }

    #define Flan void
    Flan IsMyWife()
    {
        Input();
        Soviet();
    }
}
int main()
{
    Flandre_Scarlet::IsMyWife();
    getchar();getchar();
    return 0;
}
w