程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 1573 X問題 (中國剩余定理)

HDU 1573 X問題 (中國剩余定理)

編輯:C++入門知識

HDU 1573 X問題 (中國剩余定理)


 

【題目大意】:求在小於等於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)。

【思路】中國剩余定理的應用,注意是求滿足一定條件的個數

代碼:

 

/*
* Problem: HDU No.1573
* Running time: 0MS
* Complier: G++
* Author: javaherongwei
* Create Time:  10:39 2015/9/19 星期六
* 中國剩余定理的特殊情況:ai不一定相互互質
*/
#include 
#include 
#include 
#include 
using namespace std;

typedef long long LL;
const int N=15;
LL a[N],b[N];
LL n,m,ans,m1,r1,m2,r2,c,x,t;
bool ok;
int tt;

void ex_gcd(LL a,LL b,LL &d,LL &x,LL &y){/// a*x+b*y=gcd(a,b)=d;(x,y) 為其一組整數解
    if(!b){
        d=a,x=1,y=0;
    }
    else{
        ex_gcd(b,a%b,d,y,x);
        y-=x*(a/b);
    }
}

LL ex_crt(LL *a,LL *b,LL n){
    LL x,y,d;
    m1=a[0],r1=b[0];
    for(int i=1; i

 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved