Question

一道C语言OJ题目，求余式组，我用了拓展欧几里德算法和中国剩余定理，但是还是runtime error，求解

题目：
请找出一个最小的正整数x，使得x满足（x-bi）%mi=0【i=1,2...k】；
输入：
输入有多个测试用例。每个测试用例的第一行是一个整数k （ k < 30 ），表示整数的组数。第二行有k个整数 b1, b2, … , bk ，第三行有k个正整数 m1, m2, … , mk 。
题目中给出的测试数据：
3
1 2 3
2 3 5
我的答案：
#include<stdio.h>//拓展欧几里德算法的实现（自定义递归函数）
__int64 Gcd(__int64 a,__int64 x,__int64 b,__int64 y)//拓展欧几里德算法
{
__int64 k,z;
if(b==1)
return y;
if(a%b==1)
{
k=(a-1)/b;
z=x-y*k;
return z;
}
else
{
k=a/b;
z=x-y*k;
Gcd(b,y,a%b,z);
}
}
int main()
{
__int64 n,i,a[30],b[30],c,d,g,k,e,sum;
while(scanf("%I64d",&n)!=EOF)
{
if(n==0)break;//输入结束
k=1;sum=0;
for(i=0;i<n;i++)//输入测试用例
scanf("%I64d",&a[i]);
for(i=0;i<n;i++)
{
scanf("%I64d",&b[i]);
k=k*b[i];//求所有除数的积
}
if(n==1){printf("%d\n",a[0]);continue;}//特殊处理n==1的情况
for(i=0;i<n;i++)//转化为求余式组
{
while(a[i]<0)//将a[i]为负的情况转化，大于0
a[i]=a[i]+b[i];
while(a[i]>=b[i])//将余数转化，小于除数
a[i]=a[i]-b[i];
}
for(i=0;i<n;i++)//中国剩余定理
{
c=k/b[i];
d=b[i];
g=c%d;
if(d==1)
{
sum=sum+0;
continue;
}
e=Gcd(d,0,g,1);
/*************************************
递归调用，此处的d、g互质，通过调用拓
展欧几里德算法来提高程序的效率，返回
中国剩余定理中 n*(k/b[i])%b[i]=1 中的n
**************************************/
if(e<=0)
e+=d;
sum=sum+e*c*a[i];//中国剩余定理所求的和
}
sum=sum%k;
printf("%d\n",sum);
}
return 0;
}

不知道OJ系统中哪组测试数据出了问题，应该是造成了死循环，但是我想不出，所以求各位大虾指教...看情况加分
题目中说错了一点，应该是TLE而不是RE，下标越界和除数为0的情况应该不会出现，可能是求余为0，但是已经处理了，还是TLE，想不出哪组数据会死循环，因为递归的函数是运用的拓展欧几里德算法，辗转求余到为1输出...求解。

Answer 1

runtime error不是死循环，应该是数组越界、除零异常、指针异常等原因
如果是杭电OJ也可能是栈溢出

追问

刚刚说完，是打错...

追答

那我就没法了，对数论不熟悉。。。

追问

悲剧...

Answer 2

runtime error不是死循环