coreBugZJ

此 blog 已弃。

EOJ 1117 剩余定理

  1/*
  2EOJ 1117 剩余定理
  3
  4
  5----问题描述：
  6
  7求正整数中满足：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
  9
 10----输入：
 11
 12输入数据的第一行为一个正整数T，表示有T组测试数据。
 13每组测试数据的第一行为一个正整数M，表示数组a和b中各有M个元素。0<M<=1000
 14接下来两行，每行各有M个正整数，分别为a和b中的元素。
 15
 16
 17----输出：
 18
 19每组输出占一行，输出满足方程组的最小正解X.
 20
 21
 22----样例输入：
 23
 242
 252
 262 3
 270 1
 283
 293 5 7
 302 3 2
 31
 32
 33----样例输出：
 34
 354
 3623
 37
 38
 39----分析：
 40
 41中国剩余定理。
 42
 43
 44*/
 45
 46
 47#include <iostream>
 48#include <cstdio>
 49
 50using namespace std;
 51
 52typedef  __int64  Lint;
 53
 54template< class T >
 55T 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
 65template< class T, class LT >
 66T 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
 79// ax = 1 (mod m)
 80// calc x
 81template< class T >
 82T 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
 90#define  K  1009
 91int k;
 92int m[ K ], b[ K ];
 93
 94Lint 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
115int 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 阅读(666) 评论(0)  编辑 收藏 引用 所属分类: ACM 、Algorithm 、Mathematics 、课内作业


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理