最后一题是好题,但是这些人太强了.
这次比赛前三题很水,第四题是个好题,本以为可以进入前 50 名,没想到这些人这么强.
一,公因子的数目
题意:给两个正数,求公因子数目.
暴力思路:数据量不大,枚举判断即可.
复杂度:O(n)
优化:先求最大公因数.
解释:极端情况下最大公因数是自身.
优化2:因数是对称出现的,只需要判断较小一半的因数.
复杂度:O(sqrt(n))
注意事项:n 恰好可以开方时,因子也是只能算一个.
二,沙漏的最大总和
题意:3*3 的小矩阵按照指定规则计算一个分数.
现在给一个大矩阵,问所有小矩阵里面,最大的分数是多少.
思路:枚举所有小矩阵,计算即可.
三,最小 XOR
题意:给两个数字 a