网站空间备案流程,学生怎样做网站,公众号登录入口官网,网站建设先进个人总结矩阵翻硬币
问题描述
小明先把硬币摆成了一个 n 行 m 列的矩阵。随后#xff0c;小明对每一个硬币分别进行一次 Q 操作。对第x行第y列的硬币进行 Q 操作的定义#xff1a;将所有第 i*x 行#xff0c;第 j*y 列的硬币进行翻转。其中i和j为任意使操作可行的正整数#xff0…
矩阵翻硬币
问题描述
小明先把硬币摆成了一个 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^100010的1000次方
思路分析小M的思路确实能够解决这个问题但是我们看看下面的数据规模就可以发现这种方法是不能解决100%的问题的。数据量太庞大了暴力的方式必然出不来结果。
如果一个硬币反转了n次后正面朝上且初始状态为反面朝上那么n一定是个奇数。根据题意“ 对第x行第y列的硬币进行 Q 操作的定义将所有第 i*x 行第 j*y 列的硬币进行翻转”。我们逆向的理解这个意思对与一个横坐标为x的硬币而言我们反转那些硬币时会需要翻转它呢答案是横坐标的x的约数。例如x9时翻转横坐标为1,3,9的时候会影响它的翻转纵坐标同理。
那么这个题目我们就可以通过求解拥有奇数个约数的数来实现在数学上这种数字又叫做完全平方数。即1,4,9,16,25......2^n
我们知道矩阵的行号和列号是从1开始的横坐标1-n纵坐标1-m那么我们需要解决的就是区间的完全平方数的个数问题最后相乘即可得到相乘是因为横坐标的翻转会影响纵坐标纵坐标的翻转也会影响横坐标。
注意这里会涉及到大数开方的问题不理解的读者可以参考JAVA应试技巧----大数开方还要注意在存储数据时采用的变量类型以及数据之间的转换。
import java.math.BigInteger;
import java.util.Arrays;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner in new Scanner(System.in);String n in.next();String m in.next();BigInteger ans (sqrt(n)).multiply(sqrt(m));System.out.println(ans);}private static BigInteger sqrt(String num) {int length num.length(); int sqrt_len 0;
// 获取长度if(length % 2 0) {sqrt_len length / 2;} else {sqrt_len length / 2 1;}BigInteger beSqrtNum new BigInteger(num);char[] ch new char[sqrt_len]; Arrays.fill(ch, 0); for(int i 0; i sqrt_len; i) { for(char j 1; j 9; j ) {ch[i] j;String s String.valueOf(ch);BigInteger sqrtNum new BigInteger(s);BigInteger squareNum sqrtNum.multiply(sqrtNum);if(squareNum.compareTo(beSqrtNum) 1) {ch[i] - 1;break;}}}return new BigInteger(String.valueOf(ch));}
}
