问题描述
小明先把硬币摆成了一个 n 行 m列的矩阵。随后，小明对每一个硬币分别进行一次 Q操作。
对第x行第y列的硬币进行Q操作的定义：将所有第 ix行，第 jy列的硬币进行翻转。其中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次方)。
==真因子==是指能整除一个给定数但不等于该数本身的因子，只有平方数的真因子个数为奇数
说人话
- Q操作：将x的倍数行和y的倍数行反转
- 一开始反面朝上的硬币数量一定是经历了奇数次反转的那些硬币，即 硬币只有被翻动奇数次才会有效果
- 对于（10，5）处的硬币：行的真因子：（1，10，2，5），列的真因子（1，5），所以一共会被翻4*2次
- 翻奇数次的前提是：行列真因子之积为奇数，即他们全是平方数，问题转化为寻找矩阵中下标均为平方数的元素个数
Try1 找n以内平方数的个数
def f(n): #运行超时
# # 返回n以内平方数的个数
# cnt = 0
# for i in range(1,n+1):
# if(n**0.5).is_integer():
# # 平方数开根号一定为整数
# cnt+=1
# return cnt
def f1(n):#通过10%
# cnt1 =0
# for i in range(1,n+1):
# if math.sqrt(i).is_integer():
# cnt1 += 1
# return cnt1
# print(f1(n)*f1(m))
try2由于遍历的数目太大导致超时，所以优化算法，用二分枚举
枚举n以内平方小于n的个数，非平方的因子数是成对出现的，只出现在前半部分，所以mid =（l+r）//2+1（+1是向上取整，防止错过平方数），最终的l代表有几组因子（翻动了几次），由于最终态为全部正面朝上，所以初态正面朝下的个数就是？？？？？
def number(x): #二分枚举 找平方不大于x的个数。100%通过
left=1 #因为真因子1，a1 b1，a2 b2，。。。k（k为开方数），
# 所以平方不大于x就表示a1，a2。。这些因子
right=x
while left<right:
mid=(left+right)//2+1 #向上取整 加1是表示看看后一位是否为平方数
if mid**2>x:
right=mid-1
else:
left=mid
return left
print(number(n)*number(m))
import os
import sys
import math
# Q操作：将x的倍数行和y的倍数行反转
# 对于（10，5）处的硬币：
# 行的真因子：（1，10，2，5），列的真因子（1，5），所以一共会被翻4*2次
# 真因子是指能整除一个给定数但不等于该数本身的因子，只有平方数的真因子个数为奇数
# 硬币只有被翻动奇数次才会有效果
# 翻奇数次的前提是：行列真因子之积为奇数，即他们全是平方数
# 问题转化为寻找矩阵中下标均为平方数的元素个数
n,m = map(int,input().split())
# def f(n): #运行超时
# # 返回n以内平方数的个数
# cnt = 0
# for i in range(1,n+1):
# if(n**0.5).is_integer():
# # 平方数开根号一定为整数
# cnt+=1
# return cnt
# def f1(n):#通过10%
# cnt1 =0
# for i in range(1,n+1):
# if math.sqrt(i).is_integer():
# cnt1 += 1
# return cnt1
# print(f1(n)*f1(m))
def number(x): #二分枚举 找平方不大于x的个数。100%通过
left=1 #因为真因子1，a1 b1，a2 b2，。。。k（k为开方数），
# 所以平方不大于x就表示a1，a2。。这些因子
right=x
while left<right:
mid=(left+right)//2+1 #向上取整 加1是表示看看后一位是否为平方数
if mid**2>x:
right=mid-1
else:
left=mid
return left
print(number(n)*number(m))
