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

历届试题矩阵翻硬币

时间限制：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

样例输出

1

数据规模和约定

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

题目链接：

　　http://lx.lanqiao.cn/problem.page?gpid=T126

题目大意：

题目思路：

　　【高精度】

　　高精度即可。

 //

 //by coolxxx

 //

 #include<iostream>

 #include<algorithm>

 #include<string>

 #include<iomanip>

 #include<memory.h>

 #include<time.h>

 #include<stdio.h>

 #include<stdlib.h>

 #include<string.h>

 #include<stdbool.h>

 #include<math.h>

 #define min(a,b) ((a)<(b)?(a):(b))

 #define max(a,b) ((a)>(b)?(a):(b))

 #define abs(a) ((a)>0?(a):(-(a)))

 #define sqr(a) (a)*(a)

 #define swap(a,b) (a)^=(b),(b)^=(a),(a)^=(b)

 #define eps 1e-8

 #define S 10000

 #define MAX 2139062143

 #define PI 3.1415926535897

 #define N 1004

 using namespace std;

 int n,m,cas,lll;

 int px[N],py[N],nn[N],mm[N];

 char sn[N],sm[N];

 void gjdprint(int a[])

 {

     int i;

     for(i=a[];i;i--)

         printf("%d",a[i]);

     puts("");

 }

 int gjdcompare(int a[],int b[])//a<b->1  a=b->0  a>b->-1

 {

     int i;

     if(a[]<b[])return ;

     if(a[]>b[])return -;

     for(i=a[];i;i--)

         if(a[i]<b[i])return ;

         else if(a[i]>b[i])return -;

     return ;

 }

 void gjdcheng(int a[],int b[],int c[])

 {

     int i,j,t[N];

     memset(t,,sizeof(t));

     t[]=a[]+b[];

     for(i=;i<=a[];i++)

         for(j=;j<=b[];j++)

             t[i+j-]+=a[i]*b[j];

     for(i=;i<=t[];i++)

         t[i+]+=t[i]/,t[i]%=;

     while(t[t[]+])t[]++;

     while(!t[t[]])t[]--;

     memcpy(c,t,sizeof(t));

 }

 int calculate(int a[],int b[])

 {

     int t[N];

     memset(t,,sizeof(t));

     gjdcheng(a,a,t);

     return gjdcompare(t,b);

 }

 int main()

 {

     #ifndef ONLINE_JUDGE

     //freopen("1.txt","r",stdin);

     //freopen("2.txt","w",stdout);

     #endif

     int i,j,x,y;

     while(~scanf("%s%s",sn,sm))

     //while(~scanf("%d",&n) && n)

     {

         memset(nn,,sizeof(nn));

         memset(mm,,sizeof(mm));

         nn[]=strlen(sn);

         mm[]=strlen(sm);

         for(i=;i<=nn[];i++)

             nn[i]=sn[nn[]-i]-'';

         for(i=;i<=mm[];i++)

             mm[i]=sm[mm[]-i]-'';

         px[]=nn[]/+;

         py[]=mm[]/+;

         for(i=px[];i;i--)

         {

             j=calculate(px,nn);

             while(j>=)

             {

                 if(j==)break;

                 px[i]++;

                 j=calculate(px,nn);

             }

             if(j==)break;

             px[i]--;

         }

         for(i=py[];i;i--)

         {

             j=calculate(py,mm);

             while(j>=)

             {

                 if(j==)break;

                 py[i]++;

                 j=calculate(py,mm);

             }

             if(j==)break;

             py[i]--;

         }

         gjdcheng(px,py,px);

         gjdprint(px);

     }

     return ;

 }

 /*

 //

 //

 */

巴特西

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

最新文章

热门文章

巴特西

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

最新文章

热门文章

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