蓝桥杯历届试题 PREV-34 矩阵翻硬币

布满荆棘的人生 2023-10-06 09:37 70阅读 0赞

历届试题 矩阵翻硬币

时间限制：1.0s 内存限制：256.0MB

问题描述

小明先把硬币摆成了一个 n 行 m 列的矩阵。  
  
　　随后，小明对每一个硬币分别进行一次 Q 操作。  
  
　　对第x行第y列的硬币进行 Q 操作的定义：将所有第 i\*x 行，第 j\*y 列的硬币进行翻转。  
  
　　其中i和j为任意使操作可行的正整数，行号和列号都是从1开始。  
  
　　当小明对所有硬币都进行了一次 Q 操作后，他发现了一个奇迹——所有硬币均为正面朝上。  
  
　　小明想知道最开始有多少枚硬币是反面朝上的。于是，他向他的好朋友小M寻求帮助。  
  
　　聪明的小M告诉小明，只需要对所有硬币再进行一次Q操作，即可恢复到最开始的状态。然而小明很懒，不愿意照做。于是小明希望你给出他更好的方法。帮他计算出答案。

输入格式

输入数据包含一行，两个正整数 n m，含义见题目描述。

输出格式

输出一个正整数，表示最开始有多少枚硬币是反面朝上的。

样例输入

2 3

样例输出

数据规模和约定

对于10%的数据，n、m <= 10^3；  
　　对于20%的数据，n、m <= 10^7；  
　　对于40%的数据，n、m <= 10^15；  
　　对于10%的数据，n、m <= 10^1000（10的1000次方）。

**题目解析：** **　　**

**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)**

**　　　　　　　　 在 c 语言或者 c++ 语言中没有 BigInteger 类，因此我们在考虑大数相乘的时候，需要解决移位和进位的问题。比如，在运算12 \* 34 时，我们在演草纸上怎样进行计算的呢? 首先 2 \* 4 = 8 没有进位，因此结果值的个位为 8 ，接下来 1 \* 4 = 4 、 2 \* 3 = 6 ， 4 + 6 = 10 ，有进位，进 1 后结果值的十位为 0 ，然后 1 \* 3 = 3 ，再加上刚才的进位 1 ，所以结果值的百位为 4 ，即最后的值为 408 。这是我们正常的计算方法，但我们需要考虑这种简单粗暴的方法怎样在计算机中实现。因此，我们这时想到将数放在数组中是一个很好的方法。比如，我们将 12 和 34 分别放在char型数组a和数组b中，结果放在数组 c 中。所以计算过程如下：**

**　　　　　　　　　　　a: \{ 1 , 2 \} b：\{ 3 , 4\}**

**　　　　　　　　　　　a\[1\] \* b\[1\] = 2 \* 4 = 8**

**　　　　　　　　　　　a\[0\] \* b\[1\] = 1 \* 4 = 4**

**　　　　　　　　　　　a\[1\] \* b\[0\] = 2 \* 3 = 6**

**　　　　　　　　　　　a\[0\] \* b\[0\] = 1 \* 3 = 3**

**　　　　　　　　　　　c：\{ 3 , 10 , 8 \} → \{ 4 , 0 , 8 \}**

**　　　　　　　　但是此时我们发现在数组中进行进位时是一件十分麻烦的事，因为若数非常大的时候，比如最后的结果出现了 \{ 9 , 12 , ... , 8\}，加入此数是一个 1000 0000 位的数，我们发现当最高位需要进位的时候，需要将这所有存储单位中的数右移一位，也就是需要移动 1000 0000 次，所以解决此问题的最好办法是将数在数组中逆序存储，当最高位需要进位的时候，只需要在最高位后再申请一个存储单元即可，也就是一定一次就可以了。比如计算 56 \* 78 时，**

**　　　　　　　　　　　a: \{ 6, 5 \} b：\{8 , 7\}**

**　　　　　　　　　　　a\[0\] \* b\[0\] = 6 \* 8 = 48**

**　　　　　　　　　　　a\[1\] \* b\[0\] = 5 \* 8 = 40**

**　　　　　　　　　　　a\[0\] \* b\[1\] = 6 \* 7 = 42**

**　　　　　　　　　　　a\[1\] \* b\[1\] = 5 \* 7 = 35**

**　　　　　　　　　　　c：\{ 48 , 82 , 35 \} → \{ 8 , 86 , 35 \} → \{ 8 , 6 , 43 \} → \{ 8 , 6 , 3 , 4 \}**

**　　　　　　　　即 56 \* 78 = 4368 。从移位和进位问题中我们就可以推敲出其规律来。所以，在解决大数相乘的时候，我们可以利用此方法来实现。**

**　　　　　　　**

**　　　大数比较： 调用 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 }