正題

題目鏈接:https://atcoder.jp/contests/agc027/tasks/agc027_d

---

題目大意

$n?n$的網(wǎng)格，每個格子填一個數(shù)要求

• 所有數(shù)各不相同
• 對于相鄰的兩個數(shù)$a_x,a_y$，$max\{a_x,a_y\}\%min\{a_x,a_y\}$相同
• 數(shù)的大小不超過$10^{15}$

---

解題思路

我們對與每一個斜角線都定義一個不相同的質(zhì)數(shù)，然后在兩個斜對角的位置就是兩個質(zhì)數(shù)的乘積。

對與剩下的格子填四周數(shù)的$lcm+1$即可。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; ll n,pri[110000],cnt,a[510][510]; bool v[110000]; ll lcm(ll x,ll y){if(!x||!y)return x+y;return x/__gcd(x,y)*y; } int main() {scanf("%lld",&n);if(n==2)return printf("4 7\n23 10")&0;for(ll i=2;i<=10000;i++){if(!v[i])pri[++cnt]=i;for(ll j=1;j<=cnt&&i*pri[j]<=10000;j++){v[i*pri[j]]=1;if(i%pri[j]==0)break;}}for(ll i=1;i<=n;i++)for(ll j=1;j<=n;j++)if(!((i+j)&1))a[i][j]=pri[(i+j)/2]*pri[n+(n+1)/2+(i-j)/2];for(ll i=1;i<=n;i++)for(ll j=1;j<=n;j++)if((i+j)&1)a[i][j]=lcm(lcm(a[i-1][j],a[i+1][j]),lcm(a[i][j+1],a[i][j-1]))+1ll;for(ll i=1;i<=n;i++,putchar('\n'))for(ll j=1;j<=n;j++)printf("%lld ",a[i][j]); }

總結(jié)

以上是生活随笔為你收集整理的AT4378-[AGC027D]ModuloMatrix【构造】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。