poj2891
难得见中级中的水题。。
一开始做,想着存下来,如下:
#include <iostream>
using namespace std;
#define LL long long
#define MAXN 100000000
LL ext_易做图(LL a, LL b, LL& x, LL& y)
{
LL t, ret;
if (!b)
{
x = 1, y = 0;
return a;
}
ret = ext_易做图(b, a%b, x, y);
t = x, x = y, y = t - a / b*y;
return ret;
}
LL modular_linear_system(LL b [], LL w [], LL k)
{
LL d, x, y, a = 0, m, n = 1, i;
for (i = 0; i < k; i++)
n *= w[i];
for (i = 0; i < k; i++)
{
m = n / w[i];
d = ext_易做图(w[i], m, x, y);
a = (a + y*m*b[i])%n;
}
return (a + n)%n;
}
int main()
{
int t;
while (cin >> t)
{
LL * r = new LL[MAXN];
LL * a = new LL[MAXN];
for (int i = 0; i < t; i++)
{
cin >> r[i] >> a[i];
}
LL ans = modular_linear_system(a, r, t);
cout << ans << endl;
}
}
就和这个主题的名字一样。。too young too 易做图...各种RE,根本没有告诉k的范围,乱猜哪行哇~
然后改了改,不存,逐个算就是了
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
#define MAXN 100000000
LL ext_易做图(LL a, LL b, LL& x, LL& y)
{
LL t, ret;
if (!b)
{
x = 1, y = 0;
return a;
}
ret = ext_易做图(b, a%b, x, y);
t = x, x = y, y = t - a / b*y;
return ret;
}
LL modular_linear(LL a, LL b, LL m)
{
LL d, x, y;
d = ext_易做图(a, m, x, y);
if (b % d != 0) return -1;
return (x * (b / d) % m + m) % m;
}
int main()
{
LL a1, a2, m1, m2, k, y;
while (cin>>k)
{
bool flag = false;
cin >> m1 >> a1;
if (k == 1) y = a1;
for (int i = 1; i < k; i++)
{
cin >> m2 >> a2;
if (flag) continue;
LL y = modular_linear(m2, a1 - a2, m1);
if (y == -1) { flag = true; continue; }
a1 = a2 + m2 * y;
m1 = m1*m2 / (__易做图(m1, m2));
a1 = (a1 % m1 + m1) % m1;
}
if (flag) cout << -1 << endl;
else cout << a1 << endl;
}
return 0;
}
补充:软件开发 , C++ ,