标题：矩阵翻硬币
小明先把硬币摆成了一个 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；
对于100%的数据，n、m <= 10^1000（10的1000次方）。
资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 2000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意：不要使用package语句。不要使用jdk1.7及以上版本的特性。
注意：主类的名字必须是：Main，否则按无效代码处理。
解析：
方案一：
题目中提示：“聪明的小M告诉小明，只需要对所有硬币再进行一次Q操作，即可恢复到最开始的状态。”
即假设所有格子硬币都是正面的，反向进行上述分析的模拟。
Scanner input = new Scanner(System.in);
int n = input.nextInt(); //硬币矩阵n行
int m = input.nextInt(); //硬币矩阵m列
int[][] arr = new int[n+1][m+1]; //定义硬币(数组大小+1的原因和题意相符，下标从1开始)
//将所有硬币变成正面（1：正面；0：反面）
for (int x = 1; x <= n; x++) {
for (int y = 1; y <= m; y++) {
arr[x][y] = 1;
}
}
//模拟Q操作
for (int x = 1; x <= n; x++) {
for (int y = 1; y <= m; y++) {
//循环行号和列好的倍数
for (int i = 1; i*x <= n; i++) {
for (int j = 1; j*y<=m; j++) {
int temp = arr[i*x][j*y];
arr[i*x][j*y] = temp==1?0:1;
}
}
}
}
int count = 0; //假设反面的数量为0
for (int x = 1; x <= n; x++) {
for (int y = 1; y <= m; y++) {
if(arr[x][y] == 0)
count++;
}
}
System.out.println(count);
由于题目有专门的描述如下：
【数据规模】
对于10%的数据，n、m <= 10^3；
对于20%的数据，n、m <= 10^7；
对于40%的数据，n、m <= 10^15；
对于100%的数据，n、m <= 10^1000（10的1000次方）。
资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 2000ms
则表示此题对执行效率有一定的要求，而进行方案一进行模拟的形式，如果数据量大的情况下，效率低，不能完全满足题目的要求。
方案二：
假设硬币矩阵如下，模拟所有硬币Q操作翻转过程如下：
1 2 3
4 5 6
7 8 9
对第一个硬币Q操作，需要翻转硬币：1，2，3，4，5，6，7，8，9（即全部）
对第二个硬币Q操作，需要翻转硬币：2，5，8
对第三个硬币Q操作，需要翻转硬币：3，6，9
对第四个硬币Q操作，需要翻转硬币：4，5，6
对第五个硬币Q操作，需要翻转硬币：5
对第六个硬币Q操作，需要翻转硬币：6
对第七个硬币Q操作，需要翻转硬币：7，8，9
对第八个硬币Q操作，需要翻转硬币：8
对第九个硬币Q操作，需要翻转硬币：9
思路：
（1）每个硬币，如果知道被翻转了几次，则可以求出该硬币初始状态是正面还是反面，翻转了奇数次硬币初始为反面，翻转了偶数次硬币为正面。
（2）通过上述数据得出规律，翻转次数=行号的约数个数*列号的约数个数，即：
第一个硬币，行号为1（约数1，只有1个），列号为1（约数1，只有1个），翻转数量=1*1=1
第二个硬币，行号为1（约数1，只有1个），列号为2（约数1，2，有2个），翻转数量=1*2=2
第三个硬币，行号为1（约数1，只有1个），列号为3（约数1，3，有2个），翻转数量=1*2=2
第四个硬币，行号为2（约数1，2，有2个），列号为1（约数1，有1个），翻转数量=2*1=2
第五个硬币，行号为2（约数1，2，有2个），列号为2（约数1，2，有2个），翻转数量=2*2=4
第六个硬币，行号为2（约数1，2，有2个），列号为3（约数1，3，有2个），翻转数量=2*2=4
第七个硬币，行号为3（约数1，3，有2个），列号为1（约数1，有1个），翻转数量=2*1=2
第八个硬币，行号为3（约数1，3，有2个），列号为2（约数1，2，有2个），翻转数量=2*2=4
第九个硬币，行号为3（约数1，3，有2个），列号为3（约数1，3，有2个），翻转数量=2*2=4
（3）实际上不需要求行号和列号的约数个数，只需要确定约数个数是奇数还是偶数即可，如何确定某个数字的约数个数是奇数还是偶数，有规律：平方数的约数个数是奇数，其它数字的约数个数为偶数，例如：
4约数（1，2，4）有三个为奇数；9的约数（1，3，9）有三个为奇数；16约数（1，2，4，8，16）有5个为奇数
5约束（1，5）有两个为偶数；10约束（1，2，5，10）有四个为偶数；15约数（1，3，5，15）有四个为偶数
（4）翻转次数=行号的约数个数*列号的约数个数；并且（奇乘奇=奇，奇乘偶=偶，偶乘偶=偶），当结果为奇数时，初始状态才是反面，则要求行号约数个数和列号的约数个数都为奇数，则要求行号和列号都为平方数。
（5）即题目含义变成了求行号范围内有几个平方数，列号范围内有几个平方数，结果为两个数字的乘积。
（6）如果循环遍历行号和列号求含有平方数的个数，效率仍然很低下，有规律：某个数字内平方数的个数等于该数字的开方取整，例如：
9里面（1，4，9）三个平方数，9的开方也等于三；
20里面（1，4，9，16）四个平方数，20的开方然后取整等于四。
（7）我们得到结论：初始为反面的个数=行号的开方 乘 列号的开方。
（8）由于行号和列号范围可以为（10的1000次方），直接用数字类型无法表示，无法使用Math.sqrt进行开方，只能将数字做为字符串进行处理。
（9）当数字字符串的长度为偶数，则开方结果的长度为（本身长度/2）；当数字字符串的长度为奇数，则开方结果的长度为（本身长度/2+1）,例如：
99长度为2，开方取整为9，长度为1；100长度为3，开方结果为10，长度为2；
（10）确定了开方长度之后，利用BigInteger和char[]数组，确定数组每一位数字求出开方结果。
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
String n = input.next(); //硬币矩阵n行
String m = input.next(); //硬币矩阵m列
BigInteger rowSqrt = sqrt(n);
BigInteger colSqrt = sqrt(m);
System.out.println(rowSqrt.multiply(colSqrt));
}
public static BigInteger sqrt(String s)
{
//数字字符串的长度为偶数，则开方结果的长度为（本身长度/2）；
//当数字字符串的长度为奇数，则开方结果的长度为（本身长度/2+1）
int len = s.length() % 2 == 0 ? s.length()/2 : s.length()/2+1; //求开方之后的字符串长度
char[] arr = new char[len]; //定义字符数组用于存放开方后的字符串
Arrays.fill(arr,'0'); //将字符数组所有元素设置为'0'
BigInteger num = new BigInteger(s); //将字符串转成BigInteger类型
for (int i = 0; i < arr.length; i++)
{
//循环确定字符数组每一位的数字
for (char c = '0'; c <= '9'; c++)
{
arr[i] = c;
BigInteger sqrtNum = new BigInteger(String.valueOf(arr));
if(sqrtNum.pow(2).compareTo(num) == 1) //当前假设数字的平方超过了数字本身，则减1操作
{
arr[i] -= 1;
break;
}
}
}
return new BigInteger(String.valueOf(arr));
}
网友评论