HDU3579 Hello Kiki 解线性同余方程的应用
很典型的看出 x≡Ai(mod Mi)求解,解线性同余方程的应用,
写完一直WA,后来仔细一看,题目要求输出的是最小的正整数解,所以当同余方程组的解为0的时候,就要输出 Mi 的最小公倍数
估计没少有人被坑吧
#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 #define e 2.718281828 //const ll INF=9999999999999; #define M 400000100 #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 aa[12],rr[12]; ll 易做图(ll a,ll b) { if(b==0) return a; return 易做图(b,a%b); } ll ex易做图(ll a,ll &x,ll b,ll &y) { if(b==0) { x=1; y=0; return a; } ll r=ex易做图(b,x,a%b,y); ll tmp=x; x=y; y=tmp-a/b*y; return r; } int main(void) { int t; int Case=0; ll n; cin>>t; while(t--) { cin>>n; ll lcm=1; for(int i=0;i<n;i++) { cin>>aa[i]; lcm=lcm*aa[i]/易做图(aa[i],lcm); } for(int i=0;i<n;i++) cin>>rr[i]; ll x0,y0; bool flag=false; for(int i=1;i<n;i++) { ll a=aa[0],b=aa[i],c=rr[i]-rr[0]; ll 易做图=ex易做图(a,x0,b,y0); if(c%易做图!=0) { flag=true; break; } ll MOD=b/易做图; x0=(x0*c/易做图%MOD+MOD)%MOD; rr[0]=aa[0]*x0+rr[0]; aa[0]*=(aa[i]/易做图); } printf("Case %d: ",++Case); if(flag) puts("-1"); else { if(rr[0]!=0) cout<<rr[0]<<endl; else cout<<lcm<<endl; } } }
补充:软件开发 , C++ ,