「AGC027D」Modulo Matrix(「AGC027D」Modulo Matrix)

题目

点这里看题目。

分析

说难也不难,说简单也不简单的题目。

\(\max \bmod \min = m\) 的限制,归结到底就是 \(m=1\):如果 \(A\) 满足 \(m=1\) 时的限制,那么 \(kA\) 就满足 \(m=k\) 时的限制,但后者就意味着 \(\max a\le \lfloor\frac{10^{15}}k\rfloor\)。简单点说,凭直觉我们也知道应该研究 \(m=1\) 的情况。

然后随便摆弄一下矩阵,随便选几个数按照随便什么方式丢到矩阵里面去。你可以发现这种填法:

任意确定第一行和第一列的元素,其余的元素可以按照 \(a_{i,j}=\operatorname{lcm}(a_{i-1,j},a_{i,j-1})+1\) 的方式生成。

任意确定第一行和第一列的元素,其余的元素可以按照 \(a_{i,j}=\operatorname{lcm}(a_{i-1,j},a_{i,j-1})+1\) 的方式生成。

这个东西当然无法满足 \(\max a\le 10^{15}\),但是它揭示了一点,就是矩阵中的元素实际上仅有若干个决定,剩下的可以通过简单的方式来生成

有可能你随便放,然后灵光乍现想到了“交错放置”的方法(至少我是这样想到的)。不过,由于“相邻”的格子间的元素才会产生关联,结合“确定一部分,生成一部分”的想法,我们可以想到先对网格二染色,然后将黑色的格子全部填上,这样白色的格子就可以直接生成了。

由于网格中最大值可以达到 \(\frac{n^2}{2}\),所以这种方法的理论最大值为 \(\frac{n^8}{16}\)。通过调整放置顺序可能会得到更紧的限制,不过事实上这玩意儿还是过不了。

下面这个想法就非常精妙了:虽然我们必须保证黑格子内的颜色不同,但是我们还可以小小地操作一下,让一个白格子周围的四个黑格子内有不少重复的质因子。网格可以被看作是行列的交叉,因此一种方法是给每一行、每一列单独赋一个质因子,每个黑格子就可以填入行列之积。此时白格子内部包含 9 种质因子。考虑到第 1000 个素数大约为 \(5\times 10^3\),这样构造出来的上界是 \(1.9\times 10^{33}\),相当于大退步。

但是,考虑到黑格子组成的斜网格对应的是更小的正网格,我们大可对于斜对角线赋值。这样每个白格子只会有 4 种质因子,构造上上界为 \(6.25\times 10^{14}\),这个就足以通过了。

小结:

  • 在网格中要熟悉二染色的看法、熟悉将网格看作交叉的看法;
  • 注意对于网格结构的常见变换,比如斜网格、正网格的对换。这个其实也就是 Chebyshev 距离和 Manhattan 距离对换的基本想法。

代码

#include <cstdio>

#define rep( i, a, b ) for( int i = (a) ; i <= (b) ; i ++ )
#define per( i, a, b ) for( int i = (a) ; i >= (b) ; i -- )

typedef long long LL;

const int MAXN = 505, MAXL = 2e5;

template<typename _T>
void read( _T &x ) {
    x = 0; char s = getchar(); bool f = false;
    while( s < '0' || '9' < s ) { f = s == '-', s = getchar(); }
    while( '0' <= s && s <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar(); }
    if( f ) x = -x;
}

template<typename _T>
void write( _T x ) {
    if( x < 0 ) putchar( '-' ), x = -x;
    if( 9 < x ) write( x / 10 );
    putchar( x % 10 + '0' );
}

int dir[4][2] = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

LL mat[MAXN][MAXN];

int prime[MAXL], pn;
bool isPrime[MAXL];

int N;

LL Gcd( LL x, LL y ) { for( LL z ; y ; z = x, x = y, y = z % y ); return x; }
LL Lcm( LL x, LL y ) { return x / Gcd( x, y ) * y; }

inline bool Inside( const int x, const int y ) {
    return 1 <= x && x <= N && 1 <= y && y <= N;
}

void EulerSieve( const int n ) {
    for( int i = 2 ; i <= n ; i ++ ) {
        if( ! isPrime[i] ) prime[++ pn] = i;
        for( int j = 1 ; j <= pn && 1ll * i * prime[j] <= n ; j ++ ) {
            isPrime[i * prime[j]] = true;
            if( ! ( i % prime[j] ) ) break;
        }
    }
}


int main() {
    EulerSieve( 1e5 );
    read( N );

    if( N == 2 ) 
        return puts( "4 7\n23 10" ), 0;
    rep( i, 1, N ) rep( j, 1, N ) if( ( i + j ) % 2 == 0 )
        mat[i][j] = 1ll * prime[( j - i + N + 1 ) / 2] * prime[( i + j ) / 2 + N];
    rep( i, 1, N ) rep( j, 1, N ) {
        if( mat[i][j] ) continue;
        mat[i][j] = 1;
        for( int k = 0, tx, ty ; k < 4 ; k ++ )
            if( Inside( tx = i + dir[k][0], ty = j + dir[k][1] ) )
                mat[i][j] = Lcm( mat[i][j], mat[tx][ty] );
        mat[i][j] ++;
    }
    rep( i, 1, N ) rep( j, 1, N )
        write( mat[i][j] ), putchar( j == N ? '\n' : ' ' );
    return 0;
}
————————

subject

Click here to see the topic.

analysis

It’s not difficult to say, it’s not easy to say.

\(\ Max \ bmod \ min = m \) limits can be summed up as \ (M = 1 \): if \ (a \) meets the limit when \ (M = 1 \), then \ (KA \) meets the limit when \ (M = k \), but the latter means \ (\ Max a \ Le \ lfloor \ frac{10 ^{15}}k \ rfloor \). Simply put, intuitively, we also know that we should study the situation of \ (M = 1 \).

Then fiddle with the matrix, choose a few numbers and throw them into the matrix in any way. You can find this filling method:

Arbitrarily determine the elements of the first row and the first column, and the other elements can be generated in the way of \ (a {I, J} = \ operatorname {LCM} (a {I-1, j}, a {I, J-1}) + 1 \).

Arbitrarily determine the elements of the first row and the first column, and the other elements can be generated in the way of \ (a {I, J} = \ operatorname {LCM} (a {I-1, j}, a {I, J-1}) + 1 \).

Of course, this thing cannot satisfy \ (\ Max a \ Le 10 ^ {15} \), but it reveals that the elements in the < strong > matrix actually have only a few decisions, and the rest can be generated in a simple way.

Maybe you put it casually, and then suddenly came up with the method of “staggered placement” (at least that’s what I thought). However, because the elements between “adjacent” lattices will be related, combined with the idea of “determining part and generating part”, we can think of dyeing grid 2 first, and then filling all the black lattices, so that the white lattices can be directly generated.

Since the maximum value in the grid can reach \ (\ frac {n ^ 2} {2} \), the theoretical maximum value of this method is \ (\ frac {n ^ 8} {16} \). By adjusting the placement order, you may get tighter restrictions, but in fact, this thing still can’t pass.

The following idea is very subtle: Although we must ensure that the colors in the black grid are different, we can also operate a little to make the four black grids around a white grid have many repeated quality factors< Strong > grid can be regarded as the intersection of rows and columns < / strong >, so one method is to assign a quality factor to each row and column separately, and each black grid can fill in the product of rows and columns. At this time, the white grid contains 9 germplasm factors. Considering that the 1000th prime is about \ (5 \ times 10 ^ 3 \), the constructed upper bound is \ (1.9 \ times 10 ^ {33} \), which is equivalent to a large backward step.

However, considering that the oblique grid composed of < strong > black grid corresponds to the smaller positive grid < / strong >, we can assign a value to the diagonal. In this way, each white grid will only have 4 germplasm factors, and the upper bound of the structure is \ (6.25 \ times 10 ^ {14} \), which is enough to pass.

Summary:

  • In the grid, we should be familiar with the view of two coloring and the view of treating the grid as cross;
  • Pay attention to the common transformation of grid structure, such as the exchange of oblique grid and positive grid. This is actually the basic idea of the exchange of Chebyshev distance and Manhattan distance.

code

#include <cstdio>

#define rep( i, a, b ) for( int i = (a) ; i <= (b) ; i ++ )
#define per( i, a, b ) for( int i = (a) ; i >= (b) ; i -- )

typedef long long LL;

const int MAXN = 505, MAXL = 2e5;

template<typename _T>
void read( _T &x ) {
    x = 0; char s = getchar(); bool f = false;
    while( s < '0' || '9' < s ) { f = s == '-', s = getchar(); }
    while( '0' <= s && s <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar(); }
    if( f ) x = -x;
}

template<typename _T>
void write( _T x ) {
    if( x < 0 ) putchar( '-' ), x = -x;
    if( 9 < x ) write( x / 10 );
    putchar( x % 10 + '0' );
}

int dir[4][2] = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

LL mat[MAXN][MAXN];

int prime[MAXL], pn;
bool isPrime[MAXL];

int N;

LL Gcd( LL x, LL y ) { for( LL z ; y ; z = x, x = y, y = z % y ); return x; }
LL Lcm( LL x, LL y ) { return x / Gcd( x, y ) * y; }

inline bool Inside( const int x, const int y ) {
    return 1 <= x && x <= N && 1 <= y && y <= N;
}

void EulerSieve( const int n ) {
    for( int i = 2 ; i <= n ; i ++ ) {
        if( ! isPrime[i] ) prime[++ pn] = i;
        for( int j = 1 ; j <= pn && 1ll * i * prime[j] <= n ; j ++ ) {
            isPrime[i * prime[j]] = true;
            if( ! ( i % prime[j] ) ) break;
        }
    }
}


int main() {
    EulerSieve( 1e5 );
    read( N );

    if( N == 2 ) 
        return puts( "4 7\n23 10" ), 0;
    rep( i, 1, N ) rep( j, 1, N ) if( ( i + j ) % 2 == 0 )
        mat[i][j] = 1ll * prime[( j - i + N + 1 ) / 2] * prime[( i + j ) / 2 + N];
    rep( i, 1, N ) rep( j, 1, N ) {
        if( mat[i][j] ) continue;
        mat[i][j] = 1;
        for( int k = 0, tx, ty ; k < 4 ; k ++ )
            if( Inside( tx = i + dir[k][0], ty = j + dir[k][1] ) )
                mat[i][j] = Lcm( mat[i][j], mat[tx][ty] );
        mat[i][j] ++;
    }
    rep( i, 1, N ) rep( j, 1, N )
        write( mat[i][j] ), putchar( j == N ? '\n' : ' ' );
    return 0;
}