邢台提供网站设计公司哪家专业,微信搜一搜排名优化,营销网站 深圳,济南公司建设网站AGC027D - Modulo Matrix
题目描述
Solution
有一个显然的想法是先填一部分格子#xff0c;剩下的格子的即为相邻格子的LCM1LCM1LCM1#xff0c;但这样填写的数呈指数级增长#xff0c;并不优秀。
我们发现一个格子的数是否可以填写只和相邻的四个格子有关系#xff0c…AGC027D - Modulo Matrix
题目描述
Solution
有一个显然的想法是先填一部分格子剩下的格子的即为相邻格子的LCM1LCM1LCM1但这样填写的数呈指数级增长并不优秀。
我们发现一个格子的数是否可以填写只和相邻的四个格子有关系因此考虑黑白染色同种颜色的各自之间互不影响。倘若我们固定了黑格子中的数则白格子的数也就能够固定。
一个巧妙的方法是给每一条黑色的主对角线固定一个素数作为权值每一条黑色的副对角线也固定一个素数作为权值且这些素数两两不同。令黑格子的权值为主对角线权值×副对角线权值白格子权值为LCM1LCM1LCM1这样数的大小就不会超过101510^{15}1015了。
#include vector
#include list
#include map
#include set
#include deque
#include queue
#include stack
#include bitset
#include algorithm
#include functional
#include numeric
#include utility
#include sstream
#include iostream
#include iomanip
#include cstdio
#include cmath
#include cstdlib
#include cctype
#include string
#include cstring
#include ctime
#include cassert
#include string.h
//#include unordered_set
//#include unordered_map
//#include bits/stdc.h#define MP(A,B) make_pair(A,B)
#define PB(A) push_back(A)
#define SIZE(A) ((int)A.size())
#define LEN(A) ((int)A.length())
#define FOR(i,a,b) for(int i(a);i(b);i)
#define fi first
#define se secondusing namespace std;templatetypename Tinline bool upmin(T x,T y) { return yx?xy,1:0; }
templatetypename Tinline bool upmax(T x,T y) { return xy?xy,1:0; }typedef long long ll;
typedef unsigned long long ull;
typedef long double lod;
typedef pairint,int PR;
typedef vectorint VI;const lod eps1e-11;
const lod piacos(-1);
const int oo130;
const ll loo1ll62;
const int mods998244353;
const int MAXN1005;
const int INF0x3f3f3f3f;//1061109567
/*--------------------------------------------------------------------*/
inline int read()
{int f1,x0; char cgetchar();while (c0||c9) { if (c-) f-1; cgetchar(); }while (c0c9) { x(x3)(x1)(c^48); cgetchar(); }return x*f;
}
ll a[MAXN][MAXN],prime[MAXN];
bool check(int x)
{for (int i2;1ll*i*ix;i)if (x%i0) return 0;return 1;
}
ll gcd(ll x,ll y) { return y0?x:gcd(y,x%y); }
int main()
{int nread(),num0;if (n2) { printf(4 7\n23 10\n); return 0; }for (int i2;i100000;i)if (check(i)){prime[num]i;if (numn1) break;}for (int i0;in1;i)for (int j0;jn1;j) a[i][j]1;for (int i1;in;i)for (int j1;jn;j){if ((i1)^(j1)) continue;a[i][j]prime[(ij)1]*prime[n((i-jn1)1)];}for (int i1;in;i)for (int j1;jn;j)if ((i1)^(j1)) a[i][j]max(a[i-1][j]*a[i1][j],a[i][j-1]*a[i][j1])1;if ((n1)1){a[n][1]a[n-1][1]*a[n][2]/gcd(a[n-1][1],a[n][2])1;a[1][n]a[2][n]*a[1][n-1]/gcd(a[2][n],a[1][n-1])1;}for (int i1;in;i){for (int j1;jn;j) printf(%lld ,a[i][j]);puts();}return 0;
}
