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++ ,