首页 > 代码库 > 【数论】【中国剩余定理】【LCM】hdu1788 Chinese remainder theorem again
【数论】【中国剩余定理】【LCM】hdu1788 Chinese remainder theorem again
根据题目容易得到N%Mi=Mi-a。
那么可得N%Mi+a=Mi。
两侧同时对Mi取余,可得(N+a)%Mi=0。
将N+a看成一个变量,就可以把原问题转化成求Mi的LCM,最后减去a即可。
#include<cstdio> #include<algorithm> #include<iostream> using namespace std; typedef long long ll; int K; ll a; int main(){ ll x; while(1){ cin>>K>>a; if(K==0 && a==0){ break; } ll lcm=1; for(int i=1;i<=K;++i){ scanf("%I64d",&x); lcm=lcm/__gcd(lcm,x)*x; } printf("%I64d\n",lcm-a); } return 0; }
【数论】【中国剩余定理】【LCM】hdu1788 Chinese remainder theorem again
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。