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\)书写
#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
页:
[1]