题解：ProblemG.Matrix

The 14th Jilin Provincial Collegiate Programming Contest
Changchun University of Science and Technology, September 27, 2020

题目大意

给定一个零矩阵&＃xff0c;枚举所有的点对$(i,j)$&＃xff0c;其中$i,j$均为正整数&＃xff0c;对于每一个点对$(i,j)$&＃xff0c;翻转一次满足要求的点$(m,n)$&＃xff0c;其中$m$是$i$的倍数&＃xff0c;$n$是$j$的倍数。问最后有多少为$1$的元素。翻转一次是指将元素的值$v$变成$1-v$。

我们知道对于任意一个点$(x,y)$&＃xff0c;其中$x$的约数个数为dxd_xdx​个&＃xff0c;$y$的约数个数为dyd_ydy​个&＃xff0c;那么它将翻转dx×dyd_x \times d_ydx​×dy​次&＃xff0c;这个元素为$1$&＃xff0c;当且仅当dx,dyd_x,d_ydx​,dy​均为奇数&＃xff0c;根据算数基本定理&＃xff0c;一个数的约数个数为奇数当且仅当这个数为完全平方数。

因此&＃xff0c;答案为⌊m⌋×⌊n⌋\lfloor \sqrt{m} \rfloor \times \lfloor \sqrt{n} \rfloor⌊m

​⌋×⌊n

​⌋。其中$m,n$为行数和列数。