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

问题描述

　　小明先把硬币摆成了一个 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=;
string s1,s2;     //n,m;
int len1,len2;    //记录开根号后大数的位数；

int sqrtA[],sqrtB[];
int a[];
int temp[],ans[];

int Compare(int a[],int b[],int len1,int len2) //大数比较大小 
{
    if(len1>len2) return ;
    else if(len1<len2) return -;
    for(int i=len1-;i>=;i--){
        if(a[i]>b[i]) return ;
        else if(a[i]<b[i]) return -;
    }
    return ;
}

//计算sqrtA[]*sqrtB[],len1,len2分别为sqrtA,sqrtB的长度
//返回结果位数；
int Mul(int ans[],int A[],int B[],int len1,int len2)
{
    for(int i=;i<=;i++) ans[i]=;  //对于传址ans，用memset没法初始化；
    for(int i=;i<len1;i++)
        for(int j=;j<len2;j++)
            ans[i+j]+=A[i]*B[j];
    for(int i=;i<len1+len2;i++){
        ans[i+]+=ans[i]/;
        ans[i]%=;
    }
    int i;
    for(i=len1+len2;i>=;i--)
        if(ans[i]) break;
    return i+;
}

//将s开根号,保存在a中,并且返回开根号后a的位数；
int sqrtNum(int *A,string s)
{
    memset(A,,sizeof(A));
    int len=s.size();
    int Len=len/;
    if(len%) Len+=;
    memset(a,,sizeof(a));
    for(int i=,j=s.size()-;i<s.size();i++,j--) //顺序翻转；
        a[j]=s[i]-'0';

    for(int i=Len-;i>=;i--){                //从最高位开始试；
        int flag;
        memset(temp,,sizeof(temp));
        int lenMul=;
        while((flag=Compare(temp,a,lenMul,len))==-){
            A[i]++;
            lenMul=Mul(temp,A,A,Len,Len);
        }
        if(flag==) break;
        else if(flag==) A[i]--;
    }
    return Len;
}
int main()
{
    memset(sqrtA,,sizeof(sqrtA));
    memset(sqrtB,,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-;i>=;i--) cout<<ans[i];
    cout<<endl;
    return ;
}