当前位置:编程学习 > C/C++ >>

HDU1788 Chinese remainder theorem again 中国剩余定理

首先看到的是同于方程组看到 m1,m2,m3....mk互素,这样 就可以套用中国剩余定理 的模版了,如果 m1,m2,....mk不是两两互素的话,就要解同余方程组配合扩展欧几里德
 
 
#include<iostream>  
#include<cstdio>  
#include<list>  
#include<algorithm>  
#include<cstring>  
#include<string>  
#include<queue>  
#include<stack>  
#include<map>  
#include<vector>  
#include<cmath>  
#include<memory.h>  
#include<set>  
  
#define ll long long  
#define LL __int64  
#define eps 1e-8  
  
//const ll INF=9999999999999;  
  
  
#define inf 0xfffffff  
  
using namespace std;  
  
//vector<pair<int,int> > G;  
//typedef pair<int,int> P;  
//vector<pair<int,int>> ::iterator iter;  
//  
//map<ll,int>mp;  
//map<ll,int>::iterator p;  
//  
//vector<int>G[30012];  
  
ll 易做图(ll a,ll b)  
{  
    return b==0?a:易做图(b,a%b);  
}  
  
int main(void)  
{  
    ll n,k;  
    while(cin>>n>>k,n+k)  
    {  
        ll ans=1;  
        ll m;  
        for(int i=0;i<n;i++)  
        {  
            cin>>m;  
            ans=(ans*m)/易做图(ans,m);  
        }  
        cout<<ans-k<<endl;  
    }  
}  

 


补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,