2891 -- Strange Way to Express Integers
import java.math.BigInteger;
import java.util.Scanner; public class Main {
static final BigInteger ZERO = new BigInteger("0");
static final BigInteger ONE = new BigInteger("1");
static BigInteger gcd(BigInteger a, BigInteger b) {
if (b.equals(ZERO)) return a;
else return gcd(b, a.mod(b));
}
static BigInteger lcm(BigInteger a, BigInteger b) {
return a.divide(gcd(a, b)).multiply(b);
}
static void gcd(BigInteger a, BigInteger b, BigInteger p[]) {
if (b.equals(ZERO)) {
p[0] = a;
p[1] = new BigInteger("1");
p[2] = new BigInteger("0");
} else {
gcd(b, a.mod(b), p);
BigInteger tmp = p[1];
p[1] = p[2];
p[2] = tmp;
p[2] = p[2].subtract(a.divide(b).multiply(p[1]));
}
}
static BigInteger[] A = new BigInteger[11111];
static BigInteger[] R = new BigInteger[11111];
static BigInteger work(int n) {
BigInteger[] p = new BigInteger[3];
BigInteger a = A[0], r = R[0];
for (int i = 1; i < n; i++) {
BigInteger dr = R[i].subtract(r);
gcd(a, A[i], p);
if (dr.mod(p[0]).equals(ZERO) == false) return new BigInteger("-1");
BigInteger tmp = a.multiply(p[1]);
a = lcm(a, A[i]);
tmp = tmp.mod(a).add(a).mod(a);
tmp = tmp.multiply(dr).divide(p[0]).add(r);
r = tmp.mod(a).add(a).mod(a);
}
return r;
}
public static void main(String[] args) {
int n;
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
n = in.nextInt();
String tmp;
for (int i = 0; i < n; i++) {
tmp = in.next();
A[i] = new BigInteger(tmp);
tmp = in.next();
R[i] = new BigInteger(tmp);
}
System.out.println(work(n).toString());
}
}
}
因为懒得写大数，所以直接用java的大数类来做。用这个是因为，虽然输入输出不会超过64位整型，不过中间过程还是超了。
#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring> using namespace std; typedef long long LL; const int N = ;
LL A[N], R[N];
inline LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a;}
inline LL lcm(LL a, LL b) { return a / gcd(a, b) * b;}
void gcd(LL a, LL b, LL &d, LL &x, LL &y) {
if (b) { gcd(b, a % b, d, y, x); y -= a / b * x;}
else { d = a, x = , y = ;}
} LL work(int n) {
LL x, y, d, a = A[], r = R[];
for (int i = ; i < n; i++) {
LL dr = R[i] - r;
gcd(a, A[i], d, x, y);
if (dr % d) return -;
//cout << x << ' ' << y << ' ' << d << endl;
LL tmp = a * x;
a = lcm(a, A[i]);
tmp = (tmp % a + a) % a * dr / d + r;
r = (tmp % a + a) % a;
//cout << a << ' ' << r << ' ' << tmp << endl;
}
return r ? r : a;
} int main() {
int n, T, cas = ;
cin >> T;
while (T-- && cin >> n) {
for (int i = ; i < n; i++) cin >> A[i];
for (int i = ; i < n; i++) cin >> R[i];
cout << "Case " << cas++ << ": " << work(n) << endl;
}
return ;
}
#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring> using namespace std; typedef long long LL;
inline LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a;}
inline LL lcm(LL a, LL b) { return a / gcd(a, b) * b;}
void gcd(LL a, LL b, LL &d, LL &x, LL &y) {
if (b) { gcd(b, a % b, d, y, x); y -= a / b * x;}
else d = a, x = , y = ;
} LL A[], R[], LCM;
LL work(int n) {
LL d, x, y, a = A[], r = R[];
for (int i = ; i < n; i++) {
LL dr = R[i] - r;
gcd(a, A[i], d, x, y);
//cout << d << ' ' << x << ' ' << y << endl;
if (dr % d) return -;
LL tmp = a * x * dr / d + r;
a = lcm(a, A[i]);
r = (tmp % a + a) % a;
//cout << a << '~' << r << endl;
}
LCM = a;
return r ? r : a;
} int main() {
//freopen("in", "r", stdin);
int T, n;
LL r;
cin >> T;
while (cin >> r >> n) {
for (int i = ; i < n; i++) cin >> A[i];
for (int i = ; i < n; i++) cin >> R[i];
LL ans = work(n);
//cout << ans << ' ' << LCM << endl;
if (~ans) cout << max(0ll, (r - ans + LCM) / LCM) << endl;
else puts("");
}
}
#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring> using namespace std; typedef long long LL;
inline LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a;}
inline LL lcm(LL a, LL b) { return a / gcd(a, b) * b;}
void gcd(LL a, LL b, LL &d, LL &x, LL &y) {
if (b) { gcd(b, a % b, d, y, x); y -= a / b * x;}
else d = a, x = , y = ;
} LL A[], R[]; bool check(LL a) {
for (int i = ; i < ; i++) {
if (a % > || a % <= ) return false;
a /= ;
}
return true;
} LL cal() {
LL d, x, y, a = A[], r = R[];
for (int i = ; i < ; i++) {
LL dr = R[i] - r;
gcd(a, A[i], d, x, y);
if (dr % d) {
puts("WTF??");
while () ;
}
LL tmp = a * x;
//a = lcm(a, A[i]);
a *= A[i];
tmp %= a;
tmp *= dr / d;
tmp += r;
r = (tmp % a + a) % a;
//cout << a << '~' << r << endl;
}
while (!check(r)) r += a;
//cout << r << ' ' << a << endl;
return r;
} LL cal(LL x) {
for (int i = ; i < ; i++) R[i] = x % , x /= ;
//for (int i = 0; i < 4; i++) cout << A[i] << ' ' << R[i] << endl;
return cal();
} const LL ep[] = { , , };
char out[]; int main() {
//freopen("in", "r", stdin);
int T, n, p;
LL tmp, x;
cin >> T;
while (T-- && cin >> n) {
p = ;
for (int i = ; i < ; i++) cin >> A[i];
reverse(A, A + );
for (int i = ; i < n; i++) {
cin >> tmp;
tmp = cal(tmp);
for (int i = ; i < ; i++) {
x = tmp / ep[i] % ;
out[p++] = x == ? ' ' : (x - + 'A');
}
}
out[p] = ;
while (p > && out[p - ] == ' ') out[--p] = ;
puts(out);
}
return ;
}
——written by Lyon