现在的位置: 首页 > 综合 > 正文

中国余数定理

2012年03月19日 ⁄ 综合 ⁄ 共 1730字 ⁄ 字号 评论关闭
<!--

Code highlighting produced by Actipro CodeHighlighter (freeware)
http://www.CodeHighlighter.com/

--> 1 void extended_gcd(int a,int b,int *x,int *y)
 2 {
 3     int t;
 4     if(b==0)
 5     {
 6         *= 1;
 7         *= 0;
 8         return ;
 9     }
10     extended_gcd(b,a%b,x,y);
11     t = *x;
12     *= *y;
13     *= t - a/b*(*x);
14 }
15 
16 int crt(int a[],int m[], int n)
17 {
18     int lcm,i,ans,Mi,x,y;
19     lcm = 1;
20     for(i=0;i<n;i++)
21         lcm *= m[i];
22     ans = 0;
23     for(i=0;i<n;i++)
24     {
25         Mi = lcm/m[i];
26         extended_gcd(Mi,m[i],&x,&y);
27         ans += Mi*x*a[i];
28     }
29     ans %= lcm;
30     while(ans<0)
31         ans += lcm;
32     return ans;
33 }

 

<!--

Code highlighting produced by Actipro CodeHighlighter (freeware)
http://www.CodeHighlighter.com/

-->#include <stdio.h>
#include 
<stdlib.h>

void extended_gcd(int a,int b,int *x,int *y)
{
    
int t;
    
if(b==0)
    {
        
*= 1;
        
*= 0;
        
return ;
    }
    extended_gcd(b,a
%b,x,y);
    t 
= *x;
    
*= *y;
    
*= t - a/b*(*x);
}

int crt(int a[],int m[], int n)
{
    
int lcm,i,ans,Mi,x,y;
    lcm 
= 1;
    
for(i=0;i<n;i++)
        lcm 
*= m[i];
    ans 
= 0;
    
for(i=0;i<n;i++)
    {
        Mi 
= lcm/m[i];
        extended_gcd(Mi,m[i],
&x,&y);
        ans 
+= Mi*x*a[i];
    }
    ans 
%= lcm;
    
while(ans<0)
        ans 
+= lcm;
    
return ans;
}

int main()
{
    
int i, k;
    
int *b, *m;
    
while(1)
    {
        scanf(
"%d"&k);
        b 
= (int*)malloc(sizeof(int* k);
        m 
= (int*)malloc(sizeof(int* k);
        
if(!k)
            
break;
        
for(i = 0; i < k; i ++)
            scanf(
"%d"&b[i]);
        
for(i = 0; i < k; i ++)
            scanf(
"%d"&m[i]);
        printf(
"%d
", crt(b, m, k));
        free(b);
        free(m);
    }
    
return 0;
}

 

抱歉!评论已关闭.