poj 2891 中国剩余定理
scturtle
posted @ 2010年7月16日 18:22
in algorithm
, 8066 阅读
不互质的中国剩余定理,依次合并!
假设C ≡ A1 (mod B1)，C ≡ A2 (mod B2)。令C = A1 + X1B，那么X1B1 ≡ A2 − A1 (mod B2)。用扩展欧几里德算法求出X1，也就求出C。令B = lcm(B1, B2)，那么上面两条方程就可以被C’ ≡ C (mod B)代替。迭代直到只剩下一条方程。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
__int64 x, y, t;
__int64 egcd(__int64 a, __int64 b)
{
if (b == 0)
{
x = 1;
y = 0;
return a;
}
else
{
__int64 e = egcd(b, a % b);
t = x; x = y; y = t - a / b * y;
return e;
}
}
int main()
{
//freopen("in.txt", "r", stdin);
__int64 m1, m2, r1, r2, d, c, t;
bool sb;
int n;
while (cin >> n)
{
sb = 0;
cin >> m1 >> r1;
for (int i = 0; i < n - 1; i++)
{
cin >> m2 >> r2;
if (sb) continue;
d = egcd(m1, m2);
c = r2 - r1;
if (c % d)
{
sb = 1;
continue;
}
t = m2 / d;
x = (c / d * x % t + t) % t;
r1 = m1 * x + r1;
m1 = m1 * m2 / d;
}
if (sb)
cout << -1 << endl;
else
cout << r1 << endl;
}
}
2011年7月27日 19:37
膜拜大牛，但是有些疑问，
令B = lcm(B1, B2)，那么上面两条方程就可以被C’ ≡ C (mod B)代替,
是怎么推出来的，想了很久都没有想出来，
2023年12月12日 03:19
Mastering the art of 백링크 building takes time, but the rewards are substantial. Unlock the potential of your website by creating a diverse and high-quality backlink profile.
2023年12月16日 18:16
I can't emphasize enough how much a 출장샵 session can elevate your well-being. It's a true game-changer.
2023年12月18日 23:01
인천오피's aromatherapy sessions are pure bliss. You'll leave feeling relaxed and uplifted. The attention to detail and customer care are outstanding.
2023年12月25日 22:01
해외축구중계 takes soccer seriously, just like I do. Dive into their world of international matches.
2024年1月03日 15:41
I rely on 누누티비 for my daily dose of entertainment - it never disappoints.
2024年1月11日 00:38
Pavzi website is a multiple Niche or category website which will ensure to provide information and resources on each and every topic. Some of the evergreen topics you will see on our website are Career, Job Recruitment, Educational, Technology, Reviews and others. pavzi.com We are targeting mostly so it is true that Tech, Finance, and Product Reviews. The only reason we have started this website is to make this site the need for your daily search use.
2024年1月11日 20:22
Claiming bonuses at 안전한 바카라 사이트 is simple and rewarding.
2024年1月14日 23:02
Wonderful line up. We will be linking to this wonderful article on our website. Maintain up the very good writing. เว็บคืนยอดเสีย
2024年1月16日 12:23
It’s nearly impossible to find knowledgeable men and women during this topic, however you sound like do you know what you’re discussing! Thanks link slot138
2024年1月18日 01:31
JNANABHUMI AP provides all the latest educational updates and many more. The main concept or our aim behind this website has been the will to provide resources with full information on each topic jnanabhumiap.in which can be accessed through the Internet. To ensure that every reader gets what is important and worthy about the topic they search and link to hear from us.