Question

poj 孙子问题 http://poj.grids.cn/problem/2793

#include<cstdio>
using namespace std;
void divide(int b[],int m[],int n)//高精度除法，采用类高精度取模的做法
{
int a=0,t=0;
for(int i=19;i>=0;i--)
{
t=m[i]+a*1000;
a=t%n;
b[i]=t/n;
}
}

int mod(int m[],int n)//高精度取模，网上学的，为了提高效率与方便取模，采用万进制
{
int result=0;
for(int i=19;i>=0;i--)
{
result=(result*1000+m[i])%n;
}
return result;
}

void multiply(int a[],int n)//高精度乘法
{
for(int i=0;i<20;i++)
{
a[i]*=n;
}
for(int i=0;i<20;i++)
{
if(a[i]>=1000)
{
a[i+1]+=a[i]/1000;
a[i]%=1000;
}
}

}
int gcd(int m[],int n)//高精度求最大公约数
{
int a=mod(m,n);
int t;
while(a)
{
t=a;
a=n%a;
n=t;
}
return n;
}
void euclid(int &x,int &y,int a,int b)
{
if(b==0)
{
x=1;y=0;
}
else
{
euclid(x,y,b,a%b);
int t=x;x=y;y=t-a/b*y;
}
}

int inverse(int m[],int n) //求逆
{

int a=mod(m,n);
int x,y;
euclid(x,y,n,a);
return y;
}
void output(int m[])//输出
{
int i=19;
while(m[i]==0) i--;
printf("%d",m[i--]);
for(;i>=0;i--)
{
printf("%03d",m[i]);
}
}
int main()
{
int n;
while(scanf("%d",&n)&&n!=0)
{
int m1[11][20]={0};//Mj
int a[11]={0};
int m[20]={0};
m[0]=1;
int i=0;
for(;i<n;i++)
{
scanf("%d",&a[i]);
if(gcd(m,a[i])!=1)
break;
multiply(m,a[i]);

}
if(i!=n)
printf("NO\n");
else
{
for(int i=0;i<n;i++)
{
divide(m1[i],m,a[i]);
}
for(int i=0;i<n;i++)
{
int b=inverse(m1[i],a[i]);
while(b<=0) b+=a[i];multiply(m1[i],b);
output(m1[i]);
if(i!=n-1)
printf(" ");
else
printf("\n");
}
}
}
return 0;
}

这是我的代码 ，但wa了 ，我把ai非互质的都归入NO。。所以不知道是不是因为这个WA，这个在poj 只有69人做出。。有点难度哦
这是我的新代码 还是wa，前面的函数无改
int main()
{
int n;
while(scanf("%d",&n)&&n!=0)
{
int m1[11][20]={0};//存放Mj 即a1*a2*...aj-1*aj+1*an
int a[11]={0};//存放ai
int m[20]={0};//存放M，即a1*a2*..an
m[0]=1;//c初始化一
int flag=0;
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
if(flag==1||gcd(m,a[i])!=1)//判断是否互质，若非互质则退出
flag=1;
else
multiply(m,a[i]);
}
if(flag==1)//若有非互质，则打出NO，即没有解，我不知道这样的判断有无解是否有错
printf("NO\n");
else
{
for(int i=0;i<n;i++)
{
divide(m1[i],m,a[i]);//计算Mj
}
for(int i=0;i<n;i++)
{
int b=inverse(m1[i],a[i]);//求逆元
while(b<=0) b+=a[i];multiply(m1[i],b);//计算得到大于零的逆
output(m1[i]);//以下为输出部分
if(i!=n-1)
printf(" ");
else
printf("\n");
}
}
}
return 0;
}

Answer 1

我看你基本上都写对了，非常不错

代码中有一个小问题， if(gcd(m,a[i])!=1)break;
这一句导致数据没有读完就break了，后面的测试数据接着读，所以出错了

Answer 2

不互质也可解