首页 > 代码库 > hdu 3579 Hello Kiki
hdu 3579 Hello Kiki
http://acm.hdu.edu.cn/showproblem.php?pid=3579
注意下最后的答案等于0是不行的,因为要的是正整数
#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <algorithm>using namespace std;#define inf (0x3f3f3f3f)typedef long long int LL;#include <iostream>#include <sstream>#include <vector>#include <set>#include <map>#include <queue>#include <string>const int maxn = 500 + 20;LL mod[maxn];LL r[maxn];LL gcd(LL n, LL m) { if (n % m == 0) return m; else return gcd(m, n % m);}LL lcm(LL n, LL m) { return n / gcd(n, m) * m;}LL exgcd (LL a,LL mod,LL &x,LL &y) { //求解a关于mod的逆元 ★:当且仅当a和mod互质才有用 if (mod==0) { x=1; y=0; return a;//保留基本功能,返回最大公约数 } LL g=exgcd(mod,a%mod,x,y); LL t=x; //这里根据mod==0 return回来后, x=y; //x,y是最新的值x2,y2,改变一下,这样赋值就是为了x1=y2 y=t-(a/mod)*y; // y1=x2(变成了t)-[a/mod]y2; return g; //保留基本功能,返回最大公约数}bool get_min_number (LL a,LL b,LL c,LL &x,LL &y) { //得到a*x+b*y=c的最小整数解 LL abGCD = gcd(a,b); if (c % abGCD != 0) return false;//不能整除GCD的话,此方程无解 a /= abGCD; b /= abGCD; c /= abGCD; LL tx,ty; exgcd(a,b,tx,ty); //先得到a*x+b*y=1的解,注意这个时候gcd(a,b)=1 x = tx * c; y = ty * c; //同时乘上c,c是约简了的。得到了一组a*x + b*y = c的解。 LL haveSignB = b; if (b < 0) b = -b; //避免mod负数啊,模负数没问题,模了负数后+负数就GG x = (x % b + b) % b; //最小解// if (x == 0) x = b; //避免x = 0不是"正"整数 不要用这个,溢出 y = (c - a * x) / haveSignB; return true;//true代表可以}int ff;void work() { int n; cin >> n; for (int i = 1; i <= n; ++i) { cin >> mod[i]; } for (int i = 1; i <= n; ++i) { cin >> r[i]; } LL mm = mod[1]; LL rr = r[1]; LL ansx = 1; for (int i = 2; i <= n; ++i) { LL x, y; if (get_min_number(mm, -mod[i], r[i] - rr, x, y) == false) { rr = -1; break; } ansx = mm * x + rr; mm = lcm(mm, mod[i]); rr = ansx % mm; } if (rr == 0) rr = mm; printf("Case %d: %I64d\n", ++ff, rr); return;}int main() {#ifdef local freopen("data.txt","r",stdin);#endif int t; cin >> t; while (t--) work(); return 0;}
hdu 3579 Hello Kiki
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。