HDU 1788 Chinese remainder theorem again - Vontroy

/**********************************

N % MI = MI - a

因为 a < MI

原式等价于 (N + a) % MI = 0

所以此题为求 M0 到 MI 的最小公倍数

(注意精度问题,用__int64

)

***********************************/

#include <iostream>

#include <cstdio>

using namespace std;

__int64 gcd( __int64 a, __int64 b )

{

if( b == 0 ) return a;

return gcd( b, a % b );

}

__int64 lcm( __int64 a, __int64 b )

{

return a * b / gcd( a, b );

}

int main()

{

int n, k;

int tmp;

__int64 ans;

while( cin >> n >> k, n || k )

{

ans = 1;

for( int i = 0; i < n; i++ )

{

cin >> tmp;

ans = lcm( ans, tmp );

}

cout << ans - k << endl;

}

return 0;

}

posted on 2010-10-02 14:58 Vontroy 阅读(296) 评论(0) 编辑收藏引用所属分类: 数论、HDU

只有注册用户登录后才能发表评论。
【推荐】100%开源！大型工业跨平台软件C++源码提供，建模，组态！

相关文章: POJ 1006 Biorhythms 中国剩余定理 HDU 1788 Chinese remainder theorem again 数论及数学常用知识代码 HDU 1018 Big Number 求两个或N个数的最大公约数(gcd)和最小公倍数(lcm)的较优算法

网站导航: 博客园 IT新闻 BlogJava 博问 Chat2DB 管理

随笔分类(55)