coreBugZJ

此 blog 已棄。

EOJ 1117 剩余定理

/*
2

EOJ 1117 剩余定理
3

----問題描述：
6

求正整數中滿足：X mod a[0] = b[0], X mod a[1] = b[1], X mod a[2] = b[2], …, X mod a[i] = b[i], … 的最小解。a[i]是一些兩兩互質的正整數。
8

----輸入：
11

輸入數據的第一行為一個正整數T，表示有T組測試數據。
13

每組測試數據的第一行為一個正整數M，表示數組a和b中各有M個元素。0<M<=1000
14

接下來兩行，每行各有M個正整數，分別為a和b中的元素。
15

----輸出：
18

每組輸出占一行，輸出滿足方程組的最小正解X.
20

----樣例輸入：
23

2
25

2
26

2 3
27

0 1
28

3
29

3 5 7
30

2 3 2
31

----樣例輸出：
34

4
36

23
37

----分析：
40

中國剩余定理。
42

*/
45

#include <iostream>
48

#include <cstdio>
49

using namespace std;
51

typedef __int64 Lint;
53

template< class T >
55

T gcd( T a, T b ) {
56

T t;
57

while ( 0 != b ) {
58

t = a;
59

a = b;
60

b = t % b;
61

}
62

return a;
63

}
64

template< class T, class LT >
66

T gcd_ex( T a, T b, LT &x, LT &y ) {
67

if ( b == 0 ) {
68

x = 1;
69

y = 0;
70

return a;
71

}
72

T d = gcd_ex( b, a % b, x, y );
73

LT t = x;
74

x = y;
75

y = t - ( a / b ) * y;
76

return d;
77

}
78

// ax = 1 (mod m)
80

// calc x
81

template< class T >
82

T axm( T a, T m ) {
83

T x, y;
84

if ( 1 == gcd_ex( a, m, x, y ) ) {
85

return x;
86

}
87

return 0;
88

}
89

#define K 1009
91

int k;
92

int m[ K ], b[ K ];
93

Lint solve() {
95

Lint MM = 1, M[ K ], x = 0;
96

int i;
97

for ( i = 0; i < k; ++i ) {
98

MM *= m[ i ];
99

}
100

for ( i = 0; i < k; ++i ) {
101

M[ i ] = MM / m[ i ];
102

}
103

for ( i = 0; i < k; ++i ) {
104

x += axm( M[ i ], (Lint)m[ i ] ) * M[ i ] * b[ i ];
105

if ( 0 > x ) {
106

x = MM - (-x) % MM;
107

}
108

else {
109

x = x % MM;
110

}
111

}
112

return x;
113

}
114

115

int main() {
116

int tc, i;
117

scanf( "%d", &tc );
118

while ( 0 < tc-- ) {
119

scanf( "%d", &k );
120

for ( i = 0; i < k; ++i ) {
121

scanf( "%d", m+i );
122

}
123

for ( i = 0; i < k; ++i ) {
124

scanf( "%d", b+i );
125

}
126

printf( "%I64d\n", solve() );
127

}
128

return 0;
129

}
130

posted on 2012-06-01 21:27 coreBugZJ 閱讀(707) 評論(0) 編輯收藏引用所屬分類: ACM 、Algorithm 、Mathematics 、課內作業

只有注冊用戶登錄后才能發表評論。


相關文章: 微軟2014實習生及秋令營技術類職位在線測試 TopCoder SRM 593 DIV2 第三題生成全排列的非回溯方法（TopCoder SRM 591 DIV 2） A* 算法求解八數碼問題，POJ 1077 Eight POJ 1067 取石子游戲 POJ 2068 Nim POJ 2975 Nim POJ 3696 The Luckiest number POJ 3604 Professor Ben EOJ 1117 剩余定理

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

coreBugZJ

My Links

Blog Stats

常用鏈接

留言簿(10)

隨筆分類(458)

隨筆檔案(268)

相冊

ACM

AI

LaTeX

安全

編程語言

好有道理

技術

開源

科學

數學

圖形圖像

文化

問題（練習＆有趣）

資源

最新隨筆

搜索

最新評論

閱讀排行榜

評論排行榜

EOJ 1117 剩余定理