中国剩余定理.cpp

一些比较难找的算法代码 中国剩余定理.cpp 高斯消元.cpp 红黑树.cpp 排序后第k位置数.cpp 修正单纯形.c

# include <stdio.h>
# include <string.h>
# define MAX 200

# define INPUT "%I64d"
# define OUTPUT "%I64d "
typedef __int64 I64;

struct number{
        int digit;
        I64 s[500];
};
struct set{
        I64 x,y,d;
};
set Euclid(I64 a,I64 b)
{
        set t,t1;
        if(b==0) {
                t.x=1;
                t.y=0;
                t.d=a;
        }
        else {
                t1=Euclid(b,a%b);
                t.x=t1.y;
                t.y=t1.x-(a/b)*t1.y;
                t.d=t1.d;
        }
        return t;
}
I64 Inverse(I64 a, I64 m)
{
        set t;
        t=Euclid(a,m);
        return (t.x%m+m)%m;
}
void SZDL(I64 r[],I64 m[],int n,I64 d[])
{
        int i,j;
        I64 t[MAX],s;
        for(i=0;i<n;i++) t[i]=r[i]%m[i];
        for(i=1;i<n;i++) {
                d[i-1]=t[i-1];
                for(j=i;j<n;j++) {
                        s = ((t[j]-d[i-1])%m[j]+m[j])%m[j];
                        t[j]=(s*Inverse(m[i-1],m[j]))%m[j];
                }
        }
        d[i-1]=t[i-1];
}

number add(number a,I64 n)
{
        int carry,i,temp;
        a.s[0]+=n;
        carry=0;
        for(i=0;i<a.digit;i++) {
                temp=a.s[i]+carry;
                a.s[i]=temp%10;
                carry=temp/10;  
        }               
        while(carry){
                a.s[a.digit++]=carry%10;
                carry/=10;      
        }
        return a;
}
number product(number a,I64 n)
{
        int i,temp,carry;
        for(i=0;i<a.digit;i++) a.s[i]*=n;
        carry=0;
        for(i=0;i<a.digit;i++) {
                temp=a.s[i]+carry;
                a.s[i]=temp%10;
                carry=temp/10;  
        }       
        while(carry){
                a.s[a.digit++]=carry%10;
                carry/=10;      
        }
        while(a.s[a.digit-1]==0&&a.digit>1) a.digit--;
        return a;
}
void output(number a)
{
        int i;
        for(i=a.digit-1;i>=0;i--) printf(INPUT,a.s[i]); 
}
int main()
{
        int i,n;
        I64 r[MAX],m[MAX],d[MAX];
        number ans;
        while(scanf("%d",&n)!=EOF) {
                for(i=0;i<n;i++) scanf(INPUT,&r[i]);
                for(i=0;i<n;i++) scanf(INPUT,&m[i]);
                SZDL(r,m,n,d);
                ans.s[0]=0;ans.digit=1;
                for(i=n-1;i>=0;i--){
                        ans = add(product(ans,m[i]),d[i]);      
                }
                output(ans);
                printf("\n");
        }
        return 0;
}