The 2025 Shanghai Collegiate Programming Contest-G. 矩阵（gcd(a+bx,a)=gcd(a,b)）

思路讲解

$gcd(a, b) = gcd(a-b, b)$

$gcd(a+bx,a)=gcd(a,b)$

使用如下构造方法即可。

inline void solve(){
	cin>>N;
	init();
	sieve(N+40*N);
	ll p= *upper_bound(all(primes),N);
	FOR(i,1,N){
		FOR(j,1,N){
			cout<<i*p+j<<" ";
		}
		cout<<"\n";
	}
}

AC代码

https://codeforces.com/gym/105992/my

源代码

// Problem: G. 矩阵
// Contest: Codeforces - The 2025 Shanghai Collegiate Programming Contest
// URL: https://codeforces.com/gym/105992/problem/G
// Memory Limit: 256 MB
// Time Limit: 1500 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)

using namespace std;

using  ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
// using i128 = __int128;
using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e17)+9; // 1e18+9也是素数
constexpr ll MAXM=(ll)1e6+10;constexpr ll MAXV=(ll)1e6+10;
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;const double pi=acos(-1.0);

ll N,M,Q,X,K,T,lT,A[MAXN];
/*

*/
inline void init(){
	
}
//  minp[i] 存储的是i的最小素因数
vector<ll> minp,primes;
void sieve(ll n){
	minp.assign(n+5,0);
	for(int i=2;i<=n;++i){
		if(minp[i]==0){		// 是素数
			minp[i]=i;
			primes.push_back(i);
		}
		for(auto p:primes){
			if(i*p>n){	// 超范围了
				break;
			}
			minp[i*p]=p;
			// 为了保证每个合数都只被其【最小的】那个质因数标记一次 break
			// i * p_next = (p * k) * p_next 最小的应该是p
			if(p==minp[i]){
				break;
			}
		}
	}
}
inline void solve(){
	cin>>N;
	init();
	sieve(N+40*N);
	ll p= *upper_bound(all(primes),N);
#ifdef LOCAL
    debug(p);
    for(auto ele:primes){
    	debug(ele);
    }
#endif
	FOR(i,1,N){
		FOR(j,1,N){
			cout<<i*p+j<<" ";
		}
		cout<<"\n";
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	// cin>>lT;
	// while(lT--)
		solve();
	return 0;
}
/*
AC
https://codeforces.com/gym/105992/my\\\
*/

心路历程（WA，TLE，MLE……）