[atAGC027D]Modulo Matrix
对网格图黑白染色，在黑色格中填不同的质数，白色格中填相邻黑色格的lcm+1，但这样会超过1e15的上限
将网格图划分为两类对角线，每一条对角线选一个质数，然后每一个点就是两条对角线的质数相乘，而白格的值就仅为四个较小质数的乘积+1（注意不能让两个大质数配到一起）
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 map<int,int>mat; 5 int n,p[10005],vis[10005]; 6 ll a[505][505]; 7 ll gcd(ll x,ll y){ 8 if (!y)return x; 9 return gcd(y,x%y); 10 } 11 ll lcm(ll x,ll y){ 12 if ((!x)||(!y))return x+y; 13 return x/gcd(x,y)*y; 14 } 15 int nex(int x){ 16 if (!mat[x])mat[x]=p[p[0]--]; 17 return mat[x]; 18 } 19 int main(){ 20 scanf("%d",&n); 21 if (n==2){ 22 printf("4 7 23 10 "); 23 return 0; 24 } 25 for(int i=2;i<=10000;i++){ 26 if (!vis[i])p[++p[0]]=i; 27 for(int j=1;(j<=p[0])&&(i*p[j]<=10000);j++){ 28 vis[i*p[j]]=1; 29 if (i%p[j]==0)break; 30 } 31 } 32 for(int i=1;i<=p[0]/2;i++)swap(p[i],p[p[0]-i+1]); 33 for(int i=1;i<=n;i++) 34 for(int j=1;j<=n;j++) 35 if ((i+j)%2==0)a[i][j]=nex(i+j); 36 mat.clear(); 37 for(int i=n;i;i--) 38 for(int j=n;j;j--) 39 if ((i+j)%2==0)a[i][j]*=nex(i-j); 40 for(int i=1;i<=n;i++) 41 for(int j=1;j<=n;j++) 42 if ((i+j)%2)a[i][j]=lcm(lcm(a[i-1][j],a[i][j-1]),lcm(a[i+1][j],a[i][j+1]))+1; 43 for(int i=1;i<=n;i++){ 44 for(int j=1;j<=n;j++)printf("%lld ",a[i][j]); 45 printf(" "); 46 } 47 }