1、从题目得知,如果一个硬币被翻转了奇数次后为正面朝上,那么它原始的状态一定是反面朝上。因此,我们需要统计所有翻转了奇数次硬币的个数。
2、题目中的 "对第 x 行第 y 列的硬币进行 Q 操作的定义:将所有第 i*x 行,第 j*y 列的硬币进行翻转"。我们可以试着逆向思索,对于一个横坐标为 X 的硬币而言,我们翻转那些硬币会影响到它而使它翻转呢?由此我们可以得出,当翻转的硬币的横坐标为 X 的约数时,会影响到它的翻转。比如,X=9,那么翻转横坐标为 1、3、9 的时候会影响到它的翻转。纵坐标情况同理。
对于一个硬币,我们必须考虑到它的横坐标和纵坐标。假如,此硬币的横坐标翻转了 5 次,纵坐标翻转了 6 次,那么它总的翻转次数为 5 * 6 = 30 次。因此我们得到一个公式:总翻转次数 (count) = 横坐标翻转次数 (count_x) * 纵坐标翻转次数 (count_y)。我们一开始就指出,我们需要找到翻转了奇数次的硬币,因此,横坐标翻转次数和纵坐标翻转次数均为奇数时,总翻转次数才为奇数次。
3、接下来我们需要考虑,哪些数有奇数个约数呢?答案是完全平方数。它为 1,4,9,16,25,36...... 即 n 的 2 次方,n 为从 1 开始的正整数。
从题目中得知,此时是一个 n * m 的矩阵,行号和列号都是从 1 开始。因此我们需要解决 1 到 n 之间完全平方数个数的问题。方法是求出 sqrt(n),然后对它取整,即 1 - n 之间总共由于 (int)(sqrt(n)) 个完全平方数。因此,反面朝上硬币的个数为横纵坐标完全平方数个数相乘,即 (int)((sqrt(n)) * (sqrt(m))) 。
4、由于此题的数据是超大规模的。因此,我们需要解决大数开方、大数相乘和大数比较等问题。
通常使用 String 来接受键盘输入大数,因为它的长度比较容易控制。而使用 java.math.BigInteger 包中的 BigInteger 类来存储大数据。它的原则是,只要计算机有足够的的内存,它就能存储多长位数的数。
大数开方: 牛顿逼近法。
如果一个数的位数为偶数,那么这个数的方根就有 n/2 位,如果一个数的位数为奇数,这个数的方根就有 n/2 + 1 位。
比如 num=1000 ,那么它的位数为 4 ,即方根就有 2 位。我们从方根的最高位进行枚举。
先枚举出它的十位:
10 * 10 = 100 < 1000
20 * 20 = 400 < 1000
30 * 30 = 900 < 1000
40 * 40 = 1600 > 1000
则这个根的十位为 3 。
再枚举它的个位:
31 * 31 = 961 < 1000
32 * 32 = 1024 > 1000
则这个根的个位为 1 。即这个根为 31 。
大数相乘: 调用 java.math.* 包中的 multiply 方法。比如 bigNum1.multiply(bigNum2)
大数比较: 调用 java.math.* 包中的 compareTo 方法,随第一个参数小于,等于或大于第二个参数返回负整数、零或正整数。比如 "2".compareTo ("3")
示例代码:
- 1 import java.io.BufferedReader;
- 2 import java.io.IOException;
- 3 import java.io.InputStreamReader;
- 4 import java.math.BigInteger;
- 5 import java.util.Arrays;
- 6 7 public class Main {
- 8 public static void main(String[] args) throws IOException {
- 9 BufferedReader br = new BufferedReader(new InputStreamReader(System. in ));
- 10 String[] str = br.readLine().split(" ");
- 11 String n = str[0];
- 12 String m = str[1];
- 13 BigInteger answer = (bigSqrt(n)).multiply(bigSqrt(m)); //sqrt(n) * sqrt(m) 1-n之间的完全平方数的个数 * 1-m之间完全平方数的个数
- 14 System.out.println(answer);
- 15
- }
- 16 // 求1 - num 之间完全平方数的个数
- 17 private static BigInteger bigSqrt(String num) {
- 18 int length = num.length(); //被开方数的位数
- 19 int sqrt_len = 0; //开方数的位数
- 20
- if (length % 2 == 0) {
- 21 sqrt_len = length / 2;
- 22
- } else {
- 23 sqrt_len = length / 2 + 1;
- 24
- }
- 25 BigInteger beSqrtNum = new BigInteger(num);
- 26 char[] ch = new char[sqrt_len]; //记录开方数,开房数在数组中逆序存放
- 27 Arrays.fill(ch, '0'); //将ch数组初始化为'0'
- 28
- for (int i = 0; i < sqrt_len; i++) { //从开房数的最高位开始计算,使 每一位都转化为 开方数的平方且不大于被开方数
- 29
- for (char j = '1'; j <= '9'; j++) {
- 30 ch[i] = j;
- 31 String s = String.valueOf(ch);
- 32 BigInteger sqrtNum = new BigInteger(s);
- 33 BigInteger squareNum = sqrtNum.multiply(sqrtNum);
- 34
- if (squareNum.compareTo(beSqrtNum) == 1) { //大数比较问题
- 35 ch[i] -= 1;
- 36
- break;
- 37
- }
- 38
- }
- 39
- }
- 40
- return new BigInteger(String.valueOf(ch));
- 41
- }
- 42
- }
来源: http://www.bubuko.com/infodetail-1990531.html