2025牛客多校第十场 K.神奇集合 F.老师和Yuuka逛商场 E.老师与好感度 I.矩阵 个人题解

I.矩阵

数学 #贪心 #构造

题目

思路

首先考虑有数最受条件的约束，因此尝试令数\(x\)沿着某方向前进\(x\)后回到原地：

\[\begin{align}(x+x+1)\%n-1&=x\\ \\(2x+1)\%n&=x+1\\ \\2x+1&\equiv x+1\mod n\\ \\x&\equiv 0\mod n\end{align}\]
则有\(x\)为\(n\)的因数
因此，当\(x\)为\(n\)的因数时，\(x\)无法在\(n\)方向上进行移动，\(m\)方向同理
因此，\(x=lcm(n,m)\)时，\(x\)一定无法移动
因此\(lcm(n,m)\)必须为最后一个填入的数字，可以利用这一点进行\(YES/NO\)的判断
接下来通过观察贪心地进行填空：

• 尝试将一列填满后再填下一列
  
• 尝试每填完一个数就变换一次移动方向，比如这次在列方向上向下移动，下一次列方向上的移动就向上，这样可以保证移动后不会踩到已经被填过的格子
  

代码实现

代码由\(phaethon 90\)书写
[code]#include#includeusing namespace std;#define ll long long#define endl '\n'll gcd(ll a,ll b){    if(b==0) return a;    else return gcd(b,a%b);}void eachT(){    ll n,m;    cin>>n>>m;    if(n/gcd(n,m)*m