历届试题矩阵翻硬币(数学题，大数开根)

傷城~ 2022-09-30 12:58 145阅读 0赞

### 问题描述 ###

小明先把硬币摆成了一个 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次方）。

### 题解： ###

#### 这是一个数学题，数据太大，明显不能瞎搞。肯定要推公式啊，或者找规律。 ####

#### 因为如果一个硬币在第二行，那么它可能被第一行和第二行…..等的硬币翻转。 ####

#### 我们扩展一下，如果一个硬币在第x行，那么它可能被第一行的硬币翻转的，其中y是x的约数。 ####

#### 我们把矩阵变成01矩阵。 ####

#### 0是正面，1是反面。 ####

#### 0&1=0. ####

#### 1&1=1. ####

#### 那么正反面问题就变成了一个奇偶性问题。 ####

#### 用f(x) 表示约数个数。 ####

#### 那么对答案的贡献为： ####

#### ans=∑nx=1∑my=1(f(x)∗f(y))&1 ####

#### 这个式子对101000显然也是不行的…. ####

#### 那么就再化简啊！ ####

#### 根据约数个数定理，对于一个数n，可分解成若干质数幂次的乘积. ####

#### n=prime\[1\]a∗prime\[2\]b∗..... ####

#### f(n)=(a\+1)∗(b\+1)∗...... ####

#### 其中，f(n)为n的约数个数。 ####

#### 因为奇偶性问题，所以每一项(a\+1)，(b\+1)，(c\+1)…..都是奇数。 ####

#### 所以a，b，c….这些都是偶数。 ####

#### 那么n也是偶数啊。 ####

#### 那么对答案的贡献就变成： ####

#### ans=n√∗m−−√ ####

#### 上式对于101000来说，套个大数开根模板就好了。 ####

代码：

//大数乘法
    //大数比较 
    //大数开根
    #include<bits/stdc++.h> 
    using namespace std;
    
    const int Max=1100;
    string s1,s2;     //n,m;
    int len1,len2;    //记录开根号后大数的位数；
    
    int sqrtA[1100],sqrtB[1100];
    int a[1100];
    int temp[1100],ans[1100];
    
    int Compare(int a[],int b[],int len1,int len2) //大数比较大小 
    {
        if(len1>len2) return 1;
        else if(len1<len2) return -1;
        for(int i=len1-1;i>=0;i--){
            if(a[i]>b[i]) return 1;
            else if(a[i]<b[i]) return -1;
        }
        return 0;
    }
    
    //计算sqrtA[]*sqrtB[],len1,len2分别为sqrtA,sqrtB的长度
    //返回结果位数；
    int Mul(int ans[],int A[],int B[],int len1,int len2)
    {
        for(int i=0;i<=1000;i++) ans[i]=0;  //对于传址ans，用memset没法初始化；
        for(int i=0;i<len1;i++)
            for(int j=0;j<len2;j++)
                ans[i+j]+=A[i]*B[j];
        for(int i=0;i<len1+len2;i++){
            ans[i+1]+=ans[i]/10;
            ans[i]%=10;
        }
        int i;
        for(i=len1+len2;i>=0;i--)
            if(ans[i]) break;
        return i+1;
    }
    
    //将s开根号,保存在a中,并且返回开根号后a的位数；
    int sqrtNum(int *A,string s)
    {
        memset(A,0,sizeof(A));
        int len=s.size();
        int Len=len/2;
        if(len%2) Len+=1;
        memset(a,0,sizeof(a));
        for(int i=0,j=s.size()-1;i<s.size();i++,j--) //顺序翻转；
            a[j]=s[i]-'0';
    
        for(int i=Len-1;i>=0;i--){                //从最高位开始试；
            int flag;
            memset(temp,0,sizeof(temp));
            int lenMul=1;
            while((flag=Compare(temp,a,lenMul,len))==-1){
                A[i]++;
                lenMul=Mul(temp,A,A,Len,Len);
            }
            if(flag==0) break;
            else if(flag==1) A[i]--;
        }
        return Len;
    }
    int main()
    {
        memset(sqrtA,0,sizeof(sqrtA));
        memset(sqrtB,0,sizeof(sqrtB));
    
        cin>>s1>>s2;
    
        len1=sqrtNum(sqrtA,s1);
        len2=sqrtNum(sqrtB,s2);
    
        int len=Mul(ans,sqrtA,sqrtB,len1,len2);
    
        for(int i=len-1;i>=0;i--) cout<<ans[i];
        cout<<endl;
        return 0;
    }