Python|蓝桥杯—矩阵翻硬币
问题描述
小明先把硬币摆成了一个 n 行 m 列的矩阵。随后，小明对每一个硬币分别进行一次 Q 操作。
对第x行第y列的硬币进行Q 操作的定义：将所有第 i*x 行，第 j*y 列的硬币进行翻转。其中i和j为任意使操作可行的正整数，行号和列号都是从1开始。
当小明对所有硬币都进行了一次 Q 操作后，他发现了一个奇迹——所有硬币均为正面朝上。
小明想知道最开始有多少枚硬币是反面朝上的。于是，他向他的好朋友小M寻求帮助。
聪明的小M告诉小明，只需要对所有硬币再进行一次Q操作，即可恢复到最开始的状态。然而小明很懒，不愿意照做。于是小明希望你给出他更好的方法。帮他计算出答案。
【数据格式】
输入数据包含一行，两个正整数 n m，含义见题目描述。输出一个正整数，表示最开始有多少枚硬币是反面朝上的。
【样例输入】
2 3
【样例输出】
1
【数据规模】
对于10%的数据，n、m <= 10^3；
对于20%的数据，n、m <= 10^7；
对于40%的数据，n、m <= 10^15；
对于10%的数据，n、m <= 10^1000（10的1000次方）。
资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 2000ms
解决方案
本题的思路在于找到翻动之后变成正面的硬币，有两个方向可以思考：一是对所有的硬币再次Q操作，但是题目中要求使用更加简单的方法；二是找到硬币翻动的规律，按照题目的要求，已经在暗示需要找到这个规律。
众所周知，当硬币翻动次数为奇数时，硬币面才会变化，而偶数时不变。仔细理解题目：对（x，y）点上的硬币进行Q操作的意思是对所有在矩阵中的（1*x，1*y）、（1*x，2*y）、（1*x，3*y）……满足条件的点上的硬币同时进行翻动，那么同样的对于（x，y）这一点来说，被翻动的次数就等于x的真因子和y的真因子的组合累计。例如：（2，4）这个点被翻动的次数是（1，1），（1，2），（1，4），（2，1），（2，2），（2，4），这些点在进行q操作的累计。
通过上述分析，可以得到（x，y）这一点被翻动的次数N=x的真因子个数和y的真因子个数的乘积。而且只有当奇数与奇数相乘才会得到奇数，对于自然数，只有平方数的真因子个数为奇数（质数和偶数的因子成对出现）。所以，只有当（x，y）中x和y同时为平方数的时候，这一点上的硬币被翻动后才会改变。
所以问题变成了在n*m的矩阵中找到行和列都为平方数的组合总数，且n中包含的平方数=向下取整，那么问题就类似于求*。同时还不要忘记题目中的数据规模，最后一部分数据是非常大的，使用python中开方函数无法做到，所以还需要对于这些数进行逐位的试探，找到它的平方根，详见代码。
Pytho代码：
n,m=input().split(' ')def fanyingbi(n,m): if len(n) % 2 == 0: n_len = len(n) / 2 else: n_len = (len(n) // 2) + 1 n_len = int(n_len) n_1 = [] n_2 = [] for i in range(n_len):#构建全为0的列表模拟平方根 n_1.append('0') for i in range(n_len): n_2.append('0') for x in range(n_len): for y in range(1, 10): n_1[x] = str(y)#将（1-9）插入x位置 n_2[x] = str(y - 1)#由于减了1，也不会漏掉0的情况 a = ''.join(n_1)#字符串化 b = ''.join(n_2) if eval(a) ** 2 > eval(n) and eval(b) ** 2 <= eval(n):#当x位上的数字满足条件时，跳出循环 break n_sum = eval(''.join(n_2)) if len(m) % 2 == 0: m_len = len(m) / 2 else: m_len = (len(m) // 2) + 1 m_len = int(m_len) m_1 = [] m_2 = [] for i in range(n_len):#构建全为0的列表模拟平方根 m_1.append('0') for i in range(n_len): m_2.append('0') for x in range(m_len): for y in range(1, 10): m_1[x] = str(y)#将（1-9）插入x位置 m_2[x] = str(y - 1)#同时不要忘记0的情况 a = ''.join(m_1)#字符串化 b = ''.join(m_2) if eval(a) ** 2 > eval(n) and eval(b) ** 2 <= eval(n):#当平方根满足条件时，跳出循环 break m_sum=eval(''.join(m_2)) return n_sum*m_sum |
|---|
腾讯云开发者
