13282번: Bamboo Blossoms

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

i 보다 작으면서 가장 큰 i의 약수를 pi라고 하자.
그러면 i = m부터 보면서 pi<m인 i에 대해 i-year-bamboos를 심는게 최선이다.

시간복잡도는 $O(L(t+\lg L))$

#include<cstdio>
int m, n, p[8000001];
int main() {
    for (int i = 1; i <= 8e6; i++) for (int j = i * 2; j <= 8e6; j += i) p[j] = i;
    while (scanf("%d%d", &m, &n), m) {
        for (int i = m;; i++) if (!~(n -= p[i] < m)) {
            printf("%d\n", i);
            break;
        }
    }
    return 0;
}

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;
}

1257번: 엄청난 부자

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


$\sum_{i=1}^n {A[i]*B[i]} = M (B[i]>=0)$을 만족할 때 $\sum_{i=1}^n {B[i]}$의 최댓값을 구하는 문제이다.
A[1..n]에서 A[n](=L)이 가장 크고 일단 B[n]<0이어도 된다고 하자.
어떤 k에 대해 $\sum_{i=1}^{n-1} {A[i]*B[i]} = k (mod L)$을 만족하는 $\sum_{i=1}^{n-1} {B[i]}$의 최솟값을 구해놓았다면 여기에 L짜리 동전을 x개 추가함으로써 $\sum_{i=1}^{n-1} {A[i]*B[i]} = Lx + k$ 꼴의 $\sum_{i=1}^n {B[i]}$ 최솟값을 모두 알아낼 수 있다.

문제는 x = $[M/L]$, k = M%L일 때를 구하는 것이다.

이를 이용하기 위해 L로 나눈나머지로 가능한 k = 0..L-1에 대한 노드를 만들고, 각 동전의 추가에 따라 간선을 추가한다.
i번 노드와 가치가 t인 동전에 대해
i+t < L인 경우, 단순이 t짜리 동전을 하나 추가한다는 의미에서 i -> i+t, 가중치 1인 간선을 만든다.
i+t >= L인 경우, L짜리 동전을 하나 없애고 t짜리 동전을 하나 추가한다는 의미에서 i -> i+t-L, 가중치 0인 간선을 만든다.
모든 노드와 간선을 만든 후 0에서 M%L까지의 최단 거리를 구한다. 이 값 + $[M/L]$이 답이다.

처음으로 돌아와서 B[n]<0인 경우가 과연 존재할까?
최단경로는 길어야 L-1이므로 M%L을 만들기 위해 제거한 L짜리 동전은 많아야 L-1개이다.
그런데 입력으로 주어지는 M은 10억 이상, L은 10000이하이므로 $[M/L] >= 10^6 > 9999 = L-1$.
고로 주어진 입력에 따라 본 알고리즘을 통해 구한 답은 항상 B[n]>=0이다.

아래 소스는 $O(nL\lg {nL})$

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
long long m;
int n, s, a[1000], dp[10000];
int main() {
    scanf("%lld%d", &m, &n);
    for (int i = 0; i < n; i++) scanf("%d", a + i);
    s = *max_element(a, a + n);
    for (int i = 1; i < s; i++) dp[i] = 1e9;
    priority_queue<pair<int, int> > pq;
    pq.push({ 0,0 });
    while (!pq.empty()) {
        int tdis = -pq.top().first, tpos = pq.top().second;
        pq.pop();
        if (dp[tpos] ^ tdis) continue;
        for (int i = 0; i < n; i++) {
            int t = tpos + a[i];
            if (dp[t%s] > tdis + 1 - t / s) {
                dp[t%s] = tdis + 1 - t / s;
                pq.push({ -dp[t%s],t%s });
            }
        }
    }
    printf("%lld", dp[m%s] + m / s);
    return 0;
}

13909번: 창문 닫기

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


$O(1)$

제곱 수 번호의 창문은 열려있다.

#include<cstdio>
#include<cmath>
int n;
int main() {
    scanf("%d", &n);
    printf("%d", int(sqrt(n)));
    return 0;
}

12779번: 상품 is 뭔들

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


$O(\lg(\max(a,b)))$

#include<cstdio>
#include<cmath>
typedef long long ll;
ll a, b, n, g;
ll gcd(ll x, ll y) { return y ? gcd(y, x%y) : x; }
int main() {
    scanf("%lld%lld", &a, &b);
    n = (ll)sqrt(b) - (ll)sqrt(a);
    g = gcd(n, b - a);
    n ? printf("%lld/%lld", n / g, (b - a) / g) : puts("0");
    return 0;
}

1494번: 절대값 수열

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

$O(n\lg(\min(f,s)))$

인접한 S_i와 S_i+1을 u, v라 하자.
i) u>=v*2
i가 3증가 할 때마다 u가 v*2씩 감소한다.
ii) u<v*2
u'=v
v'=abs(u-v)

연속으로 발생하는 (i)를 적절한 계산을 통해 O(1)에 모두 처리할 수 있다.
그러면 (ii)는 많아야 $O(\lg(\min(f,s)))$번 일어나므로 각 테스크를 빠르게 처리할 수 있다.

유클리디언 알고리즘의 동작 방식과 상당히 유사함을 알 수 있다.

#include<cstdio>
#include<algorithm>
using namespace std;
long long f, s, m, u, v, t;
int n;
int main() {
    for (scanf("%lld%lld%d", &f, &s, &n); n--;) {
        scanf("%lld", &m);
        u = f;
        v = s;
        while (m--) {
            swap(u, v);
            v = abs(v - u);
            t = !v || m / 3 < u / v / 2 ? m / 3 : u / v / 2;
            m -= t * 3;
            u -= t * v * 2;
        }
        printf("%lld\n", u);
    }
    return 0;
}

10872번: 팩토리얼

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


$O(n)$

#include<cstdio>
int n, r = 1;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) r *= i;
    printf("%d", r);
    return 0;
}

1676번: 팩토리얼 0의 개수

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


$O(lgn)$

#include<cstdio>
int r, n;
int main() {
    scanf("%d", &n);
    while (n /= 5) r += n;
    printf("%d", r);
    return 0;
}

2501번: 약수 구하기

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


$O(n)$

#include<cstdio>
int i, n, k;
int main() {
    scanf("%d %d", &n, &k);
    for (i = 1; i <= n&&k; i++) k -= !(n%i);
    printf("%d", k ? 0 : i - 1);
    return 0;
}

2609번: 최대공약수와 최소공배수

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


$O(lgmin(n,m))$

#include<cstdio>
int f(int x, int y) { return y ? f(y, x%y) : x; }
int n, m;
int main() {
    scanf("%d %d", &n, &m);
    printf("%d\n%d", f(n, m), n*m / f(n, m));
    return 0;
}

1934번: 최소공배수

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


$O(tlgmin(a,b))$

#include<cstdio>
int f(int x, int y) { return y ? f(y, x%y) : x; }
int t, n, m;
int main() {
    scanf("%d", &t);
    while (t--)scanf("%d %d", &n, &m), printf("%d\n", n*m / f(n, m));
    return 0;
}

11653번: 소인수분해

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


$O(\sqrt n)$

#include<cstdio>
int n;
int main() {
    scanf("%d", &n);
    for (int i = 2; i <= n; i++) while (n%i == 0) printf("%d\n", i), n /= i;
    return 0;
}

6588번: 골드바흐의 추측

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


$O(n\lg(\lg n)+tn)$

#include<cstdio>
int ck[1000000] = { 1,1 }, n;
int main() {
    for (int i = 2; i < 1e6; i++) if (!ck[i]) {
        for (int j = i * 2; j < 1e6; j += i) ck[j] = 1;
    }
    while (scanf("%d", &n), n) {
        for (int i = 1;; i++) if (!ck[i] && !ck[n - i]) {
            printf("%d = %d + %d\n", n, i, n - i);
            break;
        }
    }
    return 0;
}

2004번: 조합 0의 개수

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


$O(\lg n)$

#include<cstdio>
#include<algorithm>
using namespace std;
int n, m;
int f(int x, int y) { return x ? f(x / y, y) + x / y : 0; }
int main() {
    scanf("%d%d", &n, &m);
    printf("%d", min(f(n, 5) - f(m, 5) - f(n - m, 5), f(n, 2) - f(m, 2) - f(n - m, 2)));
    return 0;
}

1418번: K-세준수

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


$O(n(k+\lg n))$

1~n 수 각각 2~k 사이 소수로 소인수 분해한다.

#include<cstdio>
int n, k, r;
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) {
        int t = i;
        for (int j = 2; j <= k; j++) while (t%j == 0) t /= j;
        r += t == 1;
    }
    printf("%d", r);
    return 0;
}

11875번: MULTIGRAM

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


$O(dl)$
// d: 약수 개수
* 약수 개수의 상한:
http://math.stackexchange.com/questions/63687/bound-for-divisor-function

문자열 길이 l의 약수 d(d<l)에 대해
문자열을 d개씩 묶어 알파벳이 같은 개수씩 있는지 확인한다.
조건을 만족하는 가장 작은 d가 답이며 그러한 d가 없다면 불가능.

#include<cstdio>
#include<cstring>
int l;
char s[100001];
int main() {
    scanf("%s", s);
    l = strlen(s);
    for (int i = 1; i<l; i++) {
        if (l%i) continue;
        int c1[128] = { 0, };
        for (int j = 0; j<i; j++) c1[s[j]]++;
        for (int j = i; j<l; j += i) {
            int c2[128] = { 0, };
            for (int k = j; k<j + i; k++) if (++c2[s[k]]>c1[s[k]]) goto bb;
        }
        s[i] = 0;
        puts(s);
        return 0;
    bb:;
    }
    puts("-1");
    return 0;
}

3711번: 학번

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


$O(na)$

m값을 올리면서 모두 다른지 체크한다.

#include<cstdio>
int main() {
    int n;
    for (scanf("%d", &n); n; n--) {
        int g, a[300], ck[1000000] = { 0, };
        scanf("%d", &g);
        for (int i = 0; i < g; i++) scanf("%d", a + i);
        for (int i = 1;; i++) {
            int j = 0;
            for (; j < g&&ck[a[j] % i] ^ i; j++) ck[a[j] % i] = i;
            if (j == g) {
                printf("%d\n", i);
                break;
            }
        }
    }
    return 0;
}

$O(ng^2\sqrt a)$

임의의 두 정수 x, y에 대해 abs(x-y)의 약수는 답이 될 수 없으므로 제외한다.

#include<cstdio>
#include<cstdlib>
int n;
int main() {
    for (scanf("%d", &n); n--;) {
        int g, a[300], i, j, k, x, ck[1000000] = { 0, };
        scanf("%d", &g);
        for (i = 0; i < g; i++) scanf("%d", a + i);
        for (i = 0; i < g; i++) for (j = i + 1; j < g; j++)
            for (k = 1, x = abs(a[i] - a[j]); k*k <= x; k++) if (x%k == 0) ck[k] = ck[x / k] = 1;
        for (i = 0; ck[++i];);
        printf("%d\n", i);
    }
    return 0;
}

6567번: Let it Bead

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


https://en.wikipedia.org/wiki/Necklace_(combinatorics)#Number_of_bracelets


포여열거정리를 이용한다.

#include<cstdio>
int pi(int x) {
    int r = x;
    for (int i = 2; i*i <= x; i++) {
        if (x%i == 0) r -= r / i;
        while (x%i == 0) x /= i;
    }
    return r - (x > 1)*r / x;
}
int pow(int x, int y) {
    if (!y) return 1;
    int r = pow(x, y / 2);
    return r*r*(y & 1 ? x : 1);
}
int c, s;
int main() {
    while (scanf("%d %d", &c, &s) && c) {
        int t = 0;
        for (int i = 1; i <= s; i++)
            if (s%i == 0) t += pi(i)*pow(c, s / i);
        printf("%d\n", (t / s + (s & 1 ? pow(c, s / 2 + 1) : (c + 1)*pow(c, s / 2) / 2)) / 2);
    }
    return 0;
}