zercal

C++博客 首页 新随笔 联系 聚合 管理
  10 Posts :: 0 Stories :: 0 Comments :: 0 Trackbacks
#include<iostream>
using namespace std;

#define maxn 10000 //数的数量
int num[maxn],lef[maxn]; //除数和余数 
long long mm[maxn],use[maxn];



//扩展欧几里德求逆元 
int extended_euclid(int a,int b,int &x,int &y) 

    
if(b==0
    

        x
=1;y=0
        
return a; 
    }
 
    
int t,d; 
    d
=extended_euclid(b,a%b,x,y); 
    t
=x; 
    x
=y; 
    y
=t-(a/b)*y; 
    
return d; 
}
 

//返回第一个正的解 n为数的数量 
long long chinaleft(int n)
{
    
int i,j,k,x,y;
    
long long pm,res;
    
for(i=0,pm=1;i<n;i++)
        pm
*=num[i];
    
for(i=0;i<n;i++)
    
{
        mm[i]
=pm/num[i];
        extended_euclid(mm[i],num[i],x,y);
        use[i]
=mm[i]*x;
    }

    
for(i=0,res=0;i<n;i++)
        res
=(res+lef[i]*use[i])%pm;
    
if(res<0) res+=pm;
    
return res;
}

这一阵子在狂啃数论,真是不喜欢这种纯数学的东西...马上都要比赛了才刚刚会中国剩余定理...真是丢脸...


 

 

posted on 2007-10-06 19:43 zercal 阅读(228) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理