2487번: 섞기 수열

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


$O(n\lg C)$

모든 사이클 크기의 최소공배수를 구한다.

#include<cstdio>
int n, a[20001], ck[20001], r = 1;
int gcd(int x, int y) { return y ? gcd(y, x%y) : x; }
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", a + i);
    for (int i = 1; i <= n; i++) {
        int j = i, cnt = 0;
        for (; !ck[j]; j = a[j]) ck[j] = 1, cnt++;
        if (cnt) r = 1LL * r*cnt / gcd(r, cnt);
    }
    printf("%d", r);
    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;
}