历届试题矩阵翻硬币（蓝桥杯）

历届试题矩阵翻硬币

时间限制：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 #include<iostream>
  2 #include<string>
  3 #include<stdio.h>
  4 using namespace std;
  5 
  6 //两个字符串相乘
  7 string strMultiply(string str1 , string str2)
  8 {
  9     string strResult = "";
 10     int len1 = str1.length();
 11     int len2 = str2.length();
 12     int num[500] = {0};
 13     int i = 0, j = 0;
 14     for(i = 0; i < len1; i++)
 15     {
 16         for(j = 0; j < len2; j++)
 17         {
 18             num[len1-1 - i + len2-1 - j] += (str1[i] - '0')*(str2[j] - '0');
 19  //           printf("num[%d]=%d=%c*%c
",(len1-1 - i + len2-1 - j),num[len1-1 - i + len2-1 - j],str1[i],str2[j]);
 20 
 21         }
 22     }
 23   //  puts("");
 24     for(i = 0; i < len1 + len2; i++)
 25     {
 26         num[i+1] += num[i] / 10;
 27 
 28         num[i] = num[i] % 10;
 29   //      printf("%d  ",num[i]);
 30     }
 31 
 32     for(i = len1 + len2 - 1; i >= 0 ; i--)
 33     {
 34         if(0 != num[i]) break;
 35     }
 36 
 37     for(j = i; j >= 0; j--)
 38     {
 39         strResult += num[j] + '0';
 40     }
 41     return strResult;
 42 }
 43 
 44 //str1 * 10^pos后(即在str1后添上pos个0)，与str2作比较
 45 int compare(string str1, string str2, int pos)
 46 {
 47     int len1 = str1.length();
 48     int len2 = str2.length();
 49     if(len2 > len1+pos) return 0;
 50     if(len2 < len1+pos) return 1;
 51     int i = 0;
 52     for(i = 0; i < len2; i++)
 53     {
 54         if(str1[i]-'0' > str2[i]-'0') return 1;
 55         if(str1[i]-'0' < str2[i]-'0') return 0;
 56     }
 57     return 0;
 58 }
 59 
 60 //对大数str开方取整
 61 string sqrtLarge(string str)
 62 {
 63     int len = str.length();
 64     int i = 0;
 65     int j = 0;
 66     string strResult = "";
 67     string str1 = "";
 68     if(0 == len % 2)
 69     {         //为偶数位
 70         for(i = 0; i < len/2; i++)
 71         {
 72             for(j = 0; j < 10; j++)
 73             {
 74                 str1 = strResult;
 75                 str1 += j + '0';
 76                 if(1 == compare(strMultiply(str1, str1) , str , 2*(len/2-i-1)) )
 77                 {         //由于str1后少了len/2-i-1个0，所以平方以后少了2*(len/2-i-1)个
 78                     strResult +=  j-1 + '0';
 79                     break;
 80                 }
 81                 if(9 == j) strResult += '9';
 82             }
 83         }
 84     }
 85     else
 86     {       //为奇数位
 87         for(i = 0; i < len/2+1; i++)
 88         {
 89             for(j = 0; j < 10; j++)
 90             {
 91                 str1 = strResult;
 92                 str1 += j + '0';
 93                 if(1 == compare(strMultiply(str1, str1) , str , 2*(len/2-i)) )
 94                 {
 95                     strResult +=  j-1 + '0';
 96                     break;
 97                 }
 98                 if(9 == j) strResult += '9';
 99             }
100         }
101     }
102     return strResult;
103 }
104 int main()
105 {
106     string str1;
107     string str2;
108     string strResult;
109     cin>>str1>>str2;
110 
111     cout<<strMultiply(sqrtLarge(str1) , sqrtLarge(str2))<<endl;
112 
113     return 0;
114 }

历届试题 矩阵翻硬币 （蓝桥杯）

历届试题 矩阵翻硬币