# 「AGC027D」Modulo Matrix(「AGC027D」Modulo Matrix)-其他

## 「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$$ 的情况。

• 在网格中要熟悉二染色的看法、熟悉将网格看作交叉的看法；
• 注意对于网格结构的常见变换，比如斜网格、正网格的对换。这个其实也就是 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 );

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;
}

————————

### 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 );

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;
}