題意：求在小于等于N的正整數中有多少個X滿足：X mod a[0] = b[0], X mod a[1] = b[1], X mod a[2] = b[2], …, X mod a[i] = b[i], … (0 < a[i] <= 10)。

?

//#include <bits/stdc++.h> #include <iostream> #define X 10005 #define inF 0x3f3f3f3f #define PI 3.141592653589793238462643383 #define IO ios::sync_with_stdio(false),cin.tie(0), cout.tie(0); #pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std; typedef long long ll; typedef unsigned long long Ull; //2^64 const int maxn = (int)2*1e7 + 10; const int MOD = 9973;//(int)1e9 + 7; const ll inf = 9223372036854775807; //const int N = 47; ll primer[maxn]; ll a[maxn]; int ans[maxn], num[maxn]; void ex_gcd(ll a, ll b, ll &d, ll &x, ll &y) { if (!b) { x = 1; y = 0; d = a; } else { ex_gcd(b, a%b, d, y, x); y -= x * (a / b); }; } ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; } ll lcm(ll a, ll b) { return b / gcd(a, b)*a; } ll inv_exgcd(ll a, ll m) { ll d, x, y;ex_gcd(a, m, d, x, y);return d == 1 ? (x + m) % m : -1; } ll inv1(ll b) { return b == 1 ? 1 : (MOD - MOD / b)*inv1(MOD%b) % MOD; } //hdu1576用這個板子會爆除0錯誤 ll crt(int n,int *c,int *m){ll M=1,ans=0;for(int i=0;i<n;++i) M*=m[i]; for(int i=0;i<n;++i) ans=(ans+M/m[i]*c[i] %M *inv_exgcd(M/m[i],m[i]))%M; return ans;} ll N; ll ex_crt(int n,ll *m,ll *c) // X ≡ c[i] mod m[i] {ll M=m[0],R=c[0],x,y,d;for(int i=1;i<n;i++){ex_gcd(M,m[i],d,x,y);if((c[i]-R)%d) return 0;x=(c[i]-R)/d*x%(m[i]/d);R+=x*M;M=M/d*m[i];R%=M;}//R: 同余方程組的最小正整數解R=R>0?R%M:R+M;//return (R%M+M)%M; 數據卡了0if(R>N)return 0;return (N-R)/M+1;//等差數列問題 } ll f[5005]; ll sum[maxn]; ll c[maxn],m[maxn]; int cnt = 0; int main() {int t;ll M;cin>>t;while(t--){cin>>N>>M;for(int i=0;i<M;++i)cin>>m[i]; //模數for(int i=0;i<M;++i)cin>>c[i]; //余數cout<<ex_crt(M,m,c)<<endl;}return 0; }

HDU3579:

#include <bits/stdc++.h> #include <iostream> #define X 10005 #define inF 0x3f3f3f3f #define PI 3.141592653589793238462643383 #define IO ios::sync_with_stdio(false),cin.tie(0), cout.tie(0); #pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std; typedef long long ll; typedef unsigned long long Ull; //2^64 const int maxn = (int)2*1e7 + 10; const int MOD = 9973;//(int)1e9 + 7; const ll inf = 9223372036854775807; const int N = 47; ll c[maxn],m[maxn]; void ex_gcd(ll a, ll b, ll &d, ll &x, ll &y) { if (!b) { x = 1; y = 0; d = a; } else { ex_gcd(b, a%b, d, y, x); y -= x * (a / b); }; } ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; } ll lcm(ll a, ll b) { return b / gcd(a, b)*a; } ll inv_exgcd(ll a, ll m) { ll d, x, y;ex_gcd(a, m, d, x, y);return d == 1 ? (x + m) % m : -1; } ll inv1(ll b) { return b == 1 ? 1 : (MOD - MOD / b)*inv1(MOD%b) % MOD; } //hdu1576用這個板子會爆除0錯誤 ll crt(int n,int *c,int *m){ll M=1,ans=0;for(int i=0;i<n;++i) M*=m[i]; for(int i=0;i<n;++i) ans=(ans+M/m[i]*c[i] %M *inv_exgcd(M/m[i],m[i]))%M; return ans;} ll ex_crt(int n,ll *m,ll *c) // R ≡ c[i] mod m[i] {ll M=m[0],R=c[0],x,y,d;for(int i=1;i<n;i++){ex_gcd(M,m[i],d,x,y);if((c[i]-R)%d) return -1;x=(c[i]-R)/d*x%(m[i]/d);R+=x*M;M=M/d*m[i];R%=M;}return R>0?R%M:R+M;//return (R%M+M)%M; 數據卡了0 } int main() {int t,n;cin>>t;for(int ca=1;ca<=t;++ca){cin>>n;for(int i=0;i<n;++i)cin>>m[i];for(int i=0;i<n;++i)cin>>c[i];cout<<"Case "<<ca<<": "<<ex_crt(n,m,c)<<endl;}return 0; }

POJ2891：

#include <iostream> #include <cstdio> #define X 10005 #define inF 0x3f3f3f3f #define PI 3.141592653589793238462643383 #define IO ios::sync_with_stdio(false),cin.tie(0), cout.tie(0); #pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std; typedef long long ll; typedef unsigned long long Ull; //2^64 const int maxn = (int)2*1e7 + 10; const int MOD = 9973;//(int)1e9 + 7; const ll inf = 9223372036854775807; //const int N = 47; ll c[maxn],m[maxn]; void ex_gcd(ll a, ll b, ll &d, ll &x, ll &y) { if (!b) { x = 1; y = 0; d = a; } else { ex_gcd(b, a%b, d, y, x); y -= x * (a / b); }; } ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; } ll lcm(ll a, ll b) { return b / gcd(a, b)*a; } ll inv_exgcd(ll a, ll m) { ll d, x, y;ex_gcd(a, m, d, x, y);return d == 1 ? (x + m) % m : -1; } ll inv1(ll b) { return b == 1 ? 1 : (MOD - MOD / b)*inv1(MOD%b) % MOD; } //hdu1576用這個板子會爆除0錯誤 ll crt(int n,int *c,int *m){ll M=1,ans=0;for(int i=0;i<n;++i) M*=m[i]; for(int i=0;i<n;++i) ans=(ans+M/m[i]*c[i] %M *inv_exgcd(M/m[i],m[i]))%M; return ans;} ll N; ll ex_crt(int n,ll *m,ll *c)// %m[i]=c[i] {ll M=m[0],R=c[0],x,y,d;for(int i=1;i<n;++i){ex_gcd(M,m[i],d,x,y);if((c[i]-R)%d) return -1;x=(c[i]-R)/d*x%(m[i]/d);R+=x*M;M=M/d*m[i];R%=M;}return R>0?R%M:R+M; } int main() {int t;ll M;while(scanf("%d",&t)!=EOF){ //wa我不用多數據輸入for(int i=0;i<t;++i)cin>>m[i]>>c[i];cout<<ex_crt(t,m,c)<<endl;}return 0; }

?

總結

以上是生活随笔為你收集整理的【hdu 1573 X问题】【 hdu3579 Hello Kiki 】【poj 2891】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。