11069번: Particle

https://www.acmicpc.net/problem/11069

d = gcd(a, b)
(a', b') = (a / d, b / d)

주어진 직사각형을 각 변에 대한 거울상과 무한히 연결하고 이 필드 상에서 입자가 직선 운동을 한다고 생각할 수 있다.
문제의 규칙 하에 입자가 (x0, y0)에서 (x1, y1)로 속도(a', b')로 간다면 걸리는 최소 시간 tm은 다음 식을 만족하는 t(>0)중 최솟값이다.

i) x0 + a't = x1 + 2w*u  and  y0 + b't = y1 + 2h*v
ii) x0 + a't = -x1 + 2w*u  and  y0 + b't = y1 + 2h*v
iii) x0 + a't = x1 + 2w*u  and  y0 + b't = -y1 + 2h*v
iv) x0 + a't = -x1 + 2w*u and  y0 + b't = -y1 + 2h*v

이 중 (i)에 대해서만 풀어보자.
두 식은 모두 Extended Euclidean 알고리즘으로 일반해를 구할 수 있다.
첫 번째 식의 t = p1 * x + q1,
두 번째 식의 t = p2 * y + q2 라 하자.
두 t는 같아야 하므로 p1 * x + q1 = p2 * y + q2
이를 만족하는 x 역시 Extended Euclidean 알고리즘으로 일반해를 구할 수 있다.
x = p3 * x' + q3라 하면
t = p1 * x + q1 = p1*p3*x' + q1*p3 + q3
이제 위 식을 만족하면서 0보다 큰 최소 t를 구할 수 있다.

마찬가지 방법으로 (i)~(iv)에 대해 구한 t 중 최솟값 tm을 구할 수 있다.
(x2, y2)에 가는데 걸리는 최소 시간 또한 같은 방법으로 구해서 걸린 시간을 비교한다.

#include<cstdio>
#include<algorithm>
using namespace std;
int t, w, h, a0, b0, a1, b1, a2, b2, a, b;
int ee(int c1, int c2, int &r1, int &r2) {
    if (!c2) {
        r1 = 1; r2 = 0;
        return c1;
    }
    int ret = ee(c2, c1%c2, r2, r1);
    r2 -= c1 / c2*r1;
    return ret;
}
bool eq(int c1, int c2, int c3, int &r1, int &r2) {
    int u, v, ret = ee(c1, c2, u, v);
    if (c3%ret) return false;
    r1 = c2 / ret;
    r2 = 1LL * c3 / ret * u%r1;
    return true;
}
long long solve(int c1, int c2) {
    int p1, q1, p2, q2, p3, q3;
    if (!eq(a, -2 * w, c1 - a0, p1, q1) ||
        !eq(b, -2 * h, c2 - b0, p2, q2) ||
        !eq(p1, -p2, q2 - q1, p3, q3)) return 1e15;
    long long p4 = abs(1LL * p1*p3), q4 = 1LL * p1*q3 + q1;
    return (q4%p4 + p4) % p4;
}
int main() {
    for (scanf("%d", &t); t--;) {
        scanf("%d%d%d%d%d%d%d%d%d%d", &w, &h, &a0, &b0, &a1, &b1, &a2, &b2, &a, &b);
        int u, v, d = abs(ee(a, b, u, v));
        a /= d; b /= d;
        long long ret1 = min({ solve(a1, b1), solve(-a1, b1), solve(a1, -b1), solve(-a1, -b1) }),
            ret2 = min({ solve(a2, b2), solve(-a2, b2), solve(a2, -b2), solve(-a2, -b2) });
        puts(ret1^ret2 ? ret1 < ret2 ? "A" : "B" : "O");
    }
    return 0;
}

6064번: Cain Calendar

https://www.acmicpc.net/problem/6064

d = GCD(m,n)
확장 유클리드 알고리즘을 이용해 mu - nv = y-x (n/d > u >= 0, m/d > v >= 0)인 u, v를 찾는다.

시간복잡도는 테스트 케이스마다 $O(\lg(min(m,n)))$

#include<cstdio>
#include<algorithm>
int n, m, x, y, t;
int ee(int a, int b, int &u, int &v) {
    if (!b) {
        u = 1;
        v = 0;
        return a;
    }
    int ret = ee(b, a%b, v, u);
    v -= a / b*u;
    return ret;
}
int main() {
    for (scanf("%d", &t); t--;) {
        scanf("%d%d%d%d", &m, &n, &x, &y);
        int u, v, ret = ee(m, -n, u, v);
        if ((y - x) % ret) { puts("-1"); continue; }
        int p = abs(n / ret);
        printf("%d\n", (u*(y - x) / ret%p + p) % p*m + x);
    }
    return 0;
}

5627번: BAKTERIJE

https://www.acmicpc.net/problem/5627

풀이는 http://hsin.hr/coci/archive/2012_2013/에서 contest #6의 6번 참조

#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
const int dx[] = { -1,0,1,0 }, dy[] = { 0,1,0,-1 };
typedef long long ll;
int n, m, k, ex, ey, ck[51][51][4], u[51][51];
ll res = -1;
vector<pair<int, int> > v[5], pa;
int gcd(int x, int y) { return y ? gcd(y, x%y) : x; }
void ee(ll a, ll b, ll &x, ll &y) {
    if (b) ee(b, a%b, y, x), y -= a / b*x;
    else x = 1 / a, y = 0;
}
ll multi(ll x, ll y, ll mod) {
    if (!y) return 0;
    ll ret = multi(x, y / 2, mod);
    return (ret * 2 + y % 2 * x) % mod;
}
void crt() {
    int maxi = 0;
    vector<pair<int, int> > t = pa;
    for (int i = 0; i < k; i++) {
        if (maxi < t[i].second) maxi = t[i].second;
        if (!t[i].first) {
            for (auto it : t)
                if (!it.first && t[i].second != it.second || it.first && (t[i].second < it.second || (t[i].second - it.second) % it.first)) return;
            if (!~res || res > t[i].second) res = t[i].second;
            return;
        }
        for (int j = 0; j < i; j++) if ((t[i].second - t[j].second) % gcd(t[i].first, t[j].first)) return;
    }
    ll a = 1, b = 0;
    for (int i = 2; i < 1e4; i++) {
        ll tp, p = 1, r = 0, x, y, ta;
        for (int j = 0; j < k; j++) {
            tp = 1;
            while (t[j].first%i == 0) t[j].first /= i, tp *= i;
            if (p < tp) p = tp, r = t[j].second%p;
        }
        if (p > 1) {
            ee(p, a, x, y);
            ta = a*p;
            b = (multi(multi(p, x, ta), b, ta) + multi(multi(a, y, ta), r, ta)) % ta;
            a = ta;
        }
    }
    while (b < maxi) b += a;
    if (!~res || res > b) res = b;
}
void f(int h) {
    if (h == k) crt();
    else for (auto it : v[h]) {
        pa.push_back(it);
        f(h + 1);
        pa.pop_back();
    }
}
int main() {
    scanf("%d%d%d%d%d", &n, &m, &k, &ex, &ey);
    for (int i = 0; i < k; i++) {
        int x, y, d, cnt = 1;
        char c;
        scanf("%d%d %c", &x, &y, &c);
        for (int j = 1; j <= n; j++) for (int k = 1; k <= m; k++) scanf("%1d", u[j] + k);
        memset(ck, 0, sizeof(ck));
        for (int j = 0; j < 4; j++) if ("URDL"[j] == c) d = j;
        while (!ck[x][y][d]) {
            ck[x][y][d] = cnt++;
            d = (d + u[x][y]) % 4;
            if (x + dx[d] < 1 || x + dx[d] > n || y + dy[d] < 1 || y + dy[d] > m) d = (d + 2) % 4;
            x += dx[d]; y += dy[d];
        }
        for (int it : ck[ex][ey]) if (it) v[i].push_back({ it < ck[x][y][d] ? 0 : cnt - ck[x][y][d],it });
    }
    f(0);
    printf("%lld", res);
    return 0;
}

3955번: Candy Distribution

https://www.acmicpc.net/problem/3955


cy - kx = 1 (10^9>=y>=0, x>=1, y, x는 정수)을 만족하는 y를 구하는 문제
간단하게 확장 유클리드 알고리즘으로 풀 수 있다.
gcd(c,k) = d라고 하면 d=1이면 해가 존재하며 그 이외에는 해가 없다.

확장 유클리드 알고리즘으로 구한 특수해가 (x,y) = (x0, y0)라고 하면
일반해는 (x0+ct, y0+kt)로 나타낼 수 있다.
참고로 이 알고리즘을 통해 나온 특수해 (x0,y0)는 abs(x0) <= c/d * (1/d) = c, abs(y0) <= k/d * (1/d) = k 임이 보장되어있다.

테스트케이스마다 시간복잡도 $O(\lg(min(c,k)))$

#include<cstdio>
int f(int a, int b, int &x, int &y) {
    if (!b) {
        x = 1 / a;
        y = 0;
        return a;
    }
    int ret = f(b, a%b, y, x);
    y -= a / b*x;
    return ret;
}
int t, k, c;
int main() {
    for (scanf("%d", &t); t--;) {
        scanf("%d%d", &k, &c);
        int x, y, ret = f(c, -k, x, y);
        while (y <= 0) x += k, y += c;
        ret > 1 || ret < -1 || x > 1e9 ? puts("IMPOSSIBLE") : printf("%d\n", x);
    }
    return 0;
}