Archive

수학의 연산자뿐만 아니라 프로그래밍 언어의 연산자 역시 우선순위라는 개념이 존재한다. 이는 여러 가지 연산자가 포함된 수식에서 어떤 연산자를 먼저 연산해야 하는지를 지칭하는 순서이다. 우선순위가 정의되는 경우 일반적으로 두 연산자의 우선순위 관계는 불변이므로, 임의의 개수의 연산자에 대해 우선순위가 높은 순서대로 1-based index를 매길 수 있다.

FORTRAN I Compiler는 우선순위의 index를 이용하여 연산자의 연산 순위를 올바르게 반영하는 parenthesized string으로 연산식을 치환한다. 이는 우선순위 정보를 갖고 있지 않더라도 식을 평가할 수 있게 하며, 연산식 파싱을 간단한 괄호 문자열 스위핑 문제로 환원한다. 그 구체적인 알고리즘은 다음과 같이 서술할 수 있다.

1. 연산자의 우선순위가 높은 순서대로 1-based index를 부여한다. 임의의 두 연산자가 서로 우선순위가 같다면 같은 index가 부여되어도 무관하다. index가 부여된 연산자 $*$의 해당 index를 $I_*$라 하자. 또한 $M=\displaystyle\max_{\forall \text{operator }*}I_*$으로 $M$을 정의하자.
2. 연산식을 한 쌍의 괄호로 감싼다.
3. $($과 $)$를 각각 $\overbrace{((...(}^{M+1}$과 $\overbrace{))...)}^{M+1}$로 치환한다.
4. 모든 연산자 $*$에 대해 연산식 내의 $*$를 $\overbrace{))...)}^{I_*}*\overbrace{((...(}^{I_*}$로 치환한다.

$1+(2*3+4)*5$를 예시로 알고리즘을 적용해보자.

1. $I_*=1,I_+=2,M=2$
2. $(1+(2*3+4)*5)$
3. $(((1+(((2*3+4)))*5)))$
4. $(((1))+(((((2)*(3))+4))))*(5)))$

알고리즘의 결과로 $(((1))+(((((2)*(3))+4))))*(5)))$라는 수식을 얻을 수 있고, 이는 괄호만으로 원래의 연산자 계산 순서를 보장하는 문자열이다.

과연 이 알고리즘은 항상 올바른 괄호 문자열, 그것도 연산자 계산 순서를 동일하게 보장하는 문자열을 생산할까? 

Lemma 1. 입력에 괄호가 없을 경우 알고리즘은 올바른 괄호 문자열을 생산한다.

수식을 순서대로 읽을 때 $($의 개수에서 $)$의 개수를 뺀 값을 $P$라 하자. 알고리즘의 2번 단계에서 추가된 괄호에 의해 초기에 $P$는 $M+1$이다.

$M$의 정의에 의해 각각의 연산자가 치환 후 그 직전에 갖는 $)$의 개수는 $M$개 이하이므로 모든 시점에서 $P$는 1 이상이다. 또한 $*$가 치환된 $\overbrace{))...)}^{I_*}*\overbrace{((...(}^{I_*}$는 각각 ${I_*}$개의 $($과 $)$를 포함하므로 치환된 문자열을 처리하기 전과 후의 $P$는 동일하다. 따라서 각각의 연산자를 처리하며 $P$는 최소 1의 값을 가지며 마지막 $M+1$개의 $)$ 처리하기 직전에는 $P=M+1$이다. 따라서 수식을 전부 처리하면 $P=0$이므로 알고리즘의 출력은 올바른 괄호 문자열이다.

Lemma 2. 입력이 올바른 수식일 경우 알고리즘은 올바른 괄호 문자열을 생산한다.

입력에 괄호가 없는 경우는 Lemma 1에서 증명하였으므로 입력에 괄호가 존재하는 경우를 증명하자.

입력된 수식은 유한하므로, 양끝에 각각 하나의 $($와 $)$를 가지며 이외에는 괄호를 포함하지 않는 부분 수식 $(S)$를 고를 수 있다. 그렇지 않은 경우 무한히 부분 수식을 택하여 무한한 $($와 $)$가 문자열에 포함되어 수식이 유한한 길이를 갖는다는 조건에 모순된다.

이때 $(S)$가 치환된 문자열은 입력에 괄호가 없는 수식 $S$가 알고리즘에 입력됐을 때의 출력과 동일하다. Lemma 1에 의해 $(S)$가 치환된 문자열은 올바른 괄호 문자열이다.

즉 $(S)$가 치환된 문자열의 전후에서 $P$의 값이 동일하며, Lemma 1의 증명에서 언급한 것과 같이 연산자가 치환된 문자열에 의해서는 괄호 문자열이 올바르지 않게 될 수 없다. 따라서 귀납적으로 알고리즘의 전체 출력은 올바른 괄호 문자열이다.

Lemma 3. 입력에 괄호가 없을 경우 알고리즘은 연산 순서가 유지된 수식을 생산한다.

연산자가 위치한 곳에서의 $P$ 값이 높을수록 알고리즘의 출력 수식의 expression tree에서 depth가 깊다. 즉, $P$ 값이 높은 연산자일수록 먼저 계산된다. $P$ 값이 동일하며 우선순위가 서로 다른 연산자가 존재한다면 이 성질은 성립하지 않을 수 있지만, 알고리즘에 의하여 입력에 괄호가 없을 경우 어떤 연산자 $*$에서의 $P$는 $M+1-I_*$이기 때문에, 우선순위가 서로 다른 연산자는 서로 다른 $P$ 값을 가진다. 즉 위 성질이 성립하여 연산자 우선순위가 괄호에 의해 보존되게 된다.

Theorem 1. 입력이 올바른 수식일 경우 알고리즘은 연산 순서가 유지된 수식을 생산한다.

Lemma 2와 마찬가지로 양끝에 각각 하나의 $($와 $)$를 가지며 이외에는 괄호를 포함하지 않는 부분 수식 $(S)$를 고를 수 있다. $(S)$가 치환된 문자열은 입력이 $S$일 때의 Lemma 3를 적용할 수 있다. 이후 $(S)$를 포함하는 $(S)$가 아닌 최소 길이의 부분 수식 $(T)$에 대해, $(S)$는 하나의 상수 $C$로 치환하여도 수식 $(T)$의 치환 전후 연산 순서 동일성에 영향을 주지 않는다(괄호 내부는 원래 먼저 계산하므로). 따라서 $(T)$에 포함된 모든 $(S)$들을 어떤 상수로 치환하면 Lemma 3에 의해 $(T)$ 역시 치환 전후의 연산 순서가 변화하지 않는다. 이러한 논리를 귀납적으로 적용하면 입력 전체에 대해 연산 순서가 치환 전후로 변화하지 않는다는 것을 알 수 있다.

따라서 Theorem 1에 의해, 위 알고리즘은 항상 의도한 바대로 동작함을 알 수 있다.

올해 처음으로 UCPC에 참가하면서, pentagon03, jjaewon9와 함께 "새내기 개노답 삼형제"라는 팀명으로 참가하였다.

셋 다 ps에서 손을 뗀지 거진 1년이 다 되어가는 시점이었고 손을 떼기 전에도 만족스러운 실력을 갖고 있진 않았기 때문에 재활부터 시작하는 과정이 조금 어려운 감이 있었다.

나는 constructive, 수열(segtree, splay, etc), 수학을 위주로 담당하기로 하여 이를 공부하였으나 예선에서는 큰 쓸모는 없었던 듯 하다. 예선에서는 총 8문제를 풀었고 나는 A, E, H를 풀었다.

대회 시작 전 몇차례의 팀 연습에서 우리는 출제 가능성이 높은 몇가지 분야를 나누어 재활 훈련을 하였으며, 대회에서 사용할 전략을 논의했다. 별다른 것은 없지만 요약하자면 문제를 분담해서 읽고 categorizing한 뒤 각자 문제를 맡아 푸는 전략이다. 실전에서도 이러한 전략을 사용했고 그 결과 대회 진행 중 문제 분담을 효율적으로 진행할 수 있었던 것 같다.

총 10문제가 출제되어 sean9892:A,B,C,D / jjaewon9: E,F,G / pentagon03: H,I,J로 분담하여 문제를 훑었다. 예비소집에서도 언급되었듯 A는 브론즈 수준의 쉬운 문제였으므로 내가 B를 읽기 전 빠르게 A를 솔브하였다.

04:19 A RTE

05:15 A AC(+1) by sean9892

이 과정에서 코드 복사 실수로 인한 한 번의 RTE가 발생했는데, 어차피 후에 패널티를 잔뜩 섭취했기 때문에 사소하다고 할 수 있다.

A AC와 B,C,D 지문 리딩을 하던 사이 jjaewon9는 대회 시작 10분 이내에 E,G에 각각 "단순 구현"이라는 코멘트와 F에 간략한 코멘트를 남긴 채 G를 풀기 시작했다. 풀이 발상에 소요한 시간에 비해 긴 시간동안 구현 미스로 인해 패널티를 적립했다고 한다.

44:37 G TLE

47:53 G TLE

62:55 G WA

pentagon03은 H,I,J의 지문 리딩 및 요약을 무려 5분 내로 마쳤다. 마음이 급했는지 H 지문 리딩에 실수가 있긴 했으나 놀라운 리딩 속도이다. H: DP / I: 그래프DP / J: 배열정렬 정도의 간단한 코멘트를 남긴 채 H의 풀이를 잠시 고민하다 J로 넘어갔다. 역시 풀이에 비해 여러 구현 미스로 괴로워하고 있었다.

41:10 J WA

조금은 위태로운 상황이었다. 대회 시작 한 시간이 머지 않은 시점이었으나 AC는 5분에 받은 A가 전부였다. 약간의 다급함을 머금은 채 D를 풀기 시작했으나, 풀이가 좀처럼 명확해지지 않았다. multiset에서 $x$ 이하의 수의 개수를 온라인으로 셀 수 있는 자료구조가 필요하다고 생각했고 당황한 나머지(+재활을 게을리한 나머지...) 제대로 떠올리지 못하고 있었다. jjaewon9가 pbds를 써보라고 제안했지만 사용법을 몰랐고, jjaewon9가 kth 세그를 제안했다. 이거다 싶었던 나는 곧바로 구현에 들어갔고 정확히 구현했다고 생각했으나 정말 왜인지 모르겠는 의문의 출력초과 3개를 팀원들에게 선물했다. 아직도 왜 출력초과가 발생했는지는 이해하지 못했다. 팀원들의 압박감을 더하거나 덜어주려는 누군가의 계략이 분명하다고 생각한다.

50:25 D WA

58:06 D WA

64:54 D WA

이 시점에서 사실 추가선발이 아닌 본선진출은 어렵지 않을까 생각하고 있었는데, 아마 팀원 모두가 그렇게 생각하고 있었을 듯하다. 모두가 맞왜틀만을 외치기를 약 한 시간, pentagon03이 다행스럽게 J AC를 받아왔다. 머지않아 jjaewon9도 G AC를 받아왔다. 심각할 정도로 망한건 아니지 싶었다.

58:22 J AC(+1) by pentagon03

68:12 G AC(+3) by jjaewon9

내가 D에 잔뜩 출력초과를 싸놨기에 더이상 내가 이 문제를 손대는건 아닌 것 같았다. 계속 잡아도 계속 뇌절할 것 같았기에 pentagon03이 D를 넘겨받고 나는 pentagon03이 제쳐둔 H를 풀기 시작했다. jjaewon9는 스코어보드에서 많이 풀려있던 F를 풀기 시작했다. 다시 등장한 구현 미스를 딛고 jjaewon9는 109분 무렵 F AC를 받아왔다.

89:07 F WA

97:55 F WA

99:36 F WA

105:03 F WA

108:51 F AC(+4) by jjaewon9

H를 넘겨받은 나는 어쩐지 DP스럽다는 생각에 점화식을 세워보다, 카탈란 수와 유사한 점화식을 발견하였다. 이 문제는 카탈란이구나 싶어 이를 구현했으나 놓친 것들이 몇 가지 있어 한 번의 WA를 받았다. 이후로 약 40분간 더 고민한 결과 정확한 풀이를 발견하여 AC를 받았다.

83:47 H WA

119:45 H AC(+1) by sean9892

얼마 지나지 않아 pentagon03은 __int128과 내가 쓰는 방법을 몰랐던 pbds를 박아서 어찌저찌 잘 하더니 D AC를 받아왔다. 내가 출력초과를 받아놓은 게 있기 때문에 D의 패널티는 +6이 되었다.

110:28 D WA

117:03 D WA

122:29 D WA

129:26 D AC(+6) by pentagon03

프리징이 시작되었을 당시 A,F,G,H,J의 5문제를 해결하여 50 중반의 등수를 기록하고 있었다. 뒤이어 pentagon03이 받아온 D AC 덕에 등수가 제법 올랐겠지만, 남은 한 시간 동안 몇 문제는 더 풀어야 함이 명백했다. 본선... 나가고 싶었다.

B,C,E,I가 남은 상황에서 C, I는 누가 봐도 어려워보였기 때문에 버려두고 python Decimal로 E나 비벼보자는 생각에 E를 풀러갔다. jjaewon9는 B를 풀고 있었고, pentagon03은 D를 구현한 후 곧바로 jjaewon9와 함께 B를 풀기 시작했다. 선분교차를 짜야 한다고 징징대는 jjaewon9에게 해당 코드를 넘겨준 후 jjaewon9는 proof by AC를 시도하다 1WA를 적립하고, 본인은 의논이라 주장하는 모종의 독백을 한 뒤(pentagon03은 이에 "ㅇㅇ", "ㅋㅋ" 등의 반응만을 내비쳤다) 어떻게 잘 짜서 B AC를 받아왔다.

133:53 B WA

143:25 B AC(+1) by jjaewon9

잠시 뒤 python Decimal을 집어던지고 python의 datetime 모듈과 소숫점 연산의 힘을 믿은 내가 E AC를 받아왔다. 정말 놀랍게도 유일하게 패널티 없이 AC받은 문제이다.

144:55 E AC(-) by sean9892

C, I만이 남은 상황에서 팀원 모두 더이상 풀 자신이 없다는 것에 동의했다. 이후로 오간 대화는 "C 상인임?" "몰?루" "C 이거랑 같은 문제 아님?" "몰?루" 등이 전부였으며 특별상을 노려보겠다는 pentagon03의 제출을 마지막으로 예선 대회를 마무리했다. 대체 뭘 제출했길래 CE를 받은건진 모르겠다.

177:40 C WA

179:41 I CE

대회 종료 후 오픈컨테스트가 끝날 때까지 조금은 조마조마한 마음으로 시간을 보냈다. 우리 팀이 패널티를 워낙 많이 받아서 동 솔브수 팀 중 최하위일 것이라 예상했는데, 8문제를 풀었을 가능성이 있는 팀을 전부 따져보니 본선 커트라인을 넘어서는 것이다. 우리가 푼 문제 중 크게 어려운 문제가 없었으니 예선 탈락의 가능성이 있겠구나 하는 생각을 갖고 오픈컨테스트가 끝날 때까지 5시간 정도 쉬고 왔다. 다행히도 8솔브 이상인 팀이 총 30팀이었고, 예상과 동일하게 우리는 그중 최하위였다.(와!)

총평을 조금 해보자면, 재활이 덜 된 우리 팀으로써는 가능한 최대의 아웃풋을 뽑아낸게 아닌가 싶다. 총 10문제 중 8문제를 풀었으나 맞은 문제에서 틀린 횟수가 모두 합하여 17번이라는 기적적인 횟수를 일궈낸, 역사에 길이 남을 기록을 세웠다. 패널티 줄이는 연습을 할 필요가 있어보이긴 한다. 추가적으로, 플레티넘 문제도 빠르게 푸는 연습을 좀 해서 본선에서는 더 좋은 아웃풋을 내야 하지 않나 싶다. 아무튼, 잘하긴 했다. 끝.

A: 문자열 반복 + 단순 사칙연산

B: 선분교차 + 그리디

C: 몰?루 트리dp랬나 그리디랬나.

D: 좌표압축 + 세그orPBDS

E: "파이썬"

F: 단순 구현

G: constructive

H: 카탈란 수 + 올바른괄호열

I: 진짜 모름.

J: ad-hoc? 수학 쓰는 경로 압축

ICPC에서는 jjaewon9가 다른 대학이라 팀원 한 명을 구해야 하는데 누굴 데려와야 할 지 모르겠다. 흠.

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

Ad-hoc스러운 문제인 만큼, 풀이를 알면 쉬우나 풀이를 떠올리는 것이 조금 어려운 문제이다.

핵심 아이디어는 다음의 두 가지이다.

1. 임의의 자연수는 어떤 홀수 $x$와 어떤 정수 $k$에 대해 $2^k\times x$꼴로 표현된다. 특히, 짝수에 대해서는 $k$는 1 이상이다.

2. 3의 거듭제곱(1 포함)을 홀수에서 빼면 짝수가 된다.

위의 두 가지 사실을 이용하여 문제를 풀어보자.

1번에 의해 임의의 입력을 홀수로 변형할 수 있으며($N^\prime=N/2^k$), 홀수의 경우에는 2번에 의해 다시 짝수로 만들어줄 수 있다.($N^\prime=N-3^k$)

이 과정을 반복하여 문제를 해결할 때, $N$은 $2^{a_1}(3^{b_1}+2^{a_2}(3^{b_2}+...))$의 꼴로 표현된다. 모두 전개하면 $2^{a_1}3^{b_1}+2^{a_1+a_2}3^{b_2}+...$과 같이 표현된다는 사실을 알 수 있을 것이다. 이는 문제에서 요구하는 각각의 항과 동일한 꼴임을 발견할 수 있다.

이제 중요한 것은 이러한 항들이 문제 조건을 만족하는가이다. 즉, 2의 지수가 증가하는 순으로 나열했을 때 3의 지수를 감소하게끔 설정할 수 있는지가 핵심이 될 것이다.

$3^{b_i}$에 곱해진 2의 거듭제곱의 지수는 증가함이 자명하다. $a_1\le0$이며, 위의 2번 사실에 의해 2 이상의 정수 $i$에 대해 $a_i>0$이기 때문이다. 그렇다면 $b_i$가 감소수열이기만 하면 이렇게 구한 항들은 문제의 정답에 해당할 것이다.

여기서, 우리는 $b_i$의 값을 확정하지 않았음을 상기하자. 따라서 감소수열 $b_i$를 적당히 정의하기만 하면 된다. 가장 무난하며 쉽게 찾을 수 있는 선택지는 선택할 수 있는 가장 큰 3의 거듭제곱이다. 이 정의의 경우 $b_i$가 단조감소한다는 사실은 3진법 전개를 통해 쉽게 증명할 수 있으므로 독자에게 맡긴다.

위와 같은 풀이를 재귀함수 내지는 반복문을 이용하여 구현하면 AC를 받을 수 있다. 아래는 이를 구현한 코드이다.

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

void TC(){
    ll n;
    cin>>n;
    int b2=0;
    vector<int> v,w;
    while(n>0){
        while(n%2==0){
            b2++;
            n/=2;
        }
        ll r=1;
        int i;
        for(i=0;r<=n;i++,r*=3);
        r/=3;i--;
        n-=r;
        v.push_back(b2);
        w.push_back(i);
    }
    cout<<v.size()<<"\n";
    for(int i=0;i<v.size();i++){
        cout<<v[i]<<" "<<w[i]<<"\n";
    }
}

int main(void){
    ios::sync_with_stdio(0);cin.tie(0);
    int tc;
    cin>>tc;
    while(tc--){
        TC();
    }
}

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

자릿수에 관한 관찰이 필요한 문제이다. 따라서 0-based index로 $i$번째 자릿수를 $a_i$로 정의하는 것이 문제 풀이에 도움이 될 것이다.

이때 문제의 정답이 되는 최소의 자연수를 $X$, $X$를 뒤집은 수를 $\bar{X}$, $X$의 길이를 $L$이라 하자. 정의에 의해 다음의 세 가지 식이 성립한다.

1. $\displaystyle X=\sum_{i=0}^{L-1}a_i\times10^{i}$

2. $\displaystyle \bar{X}=\sum_{i=0}^{L-1}a_i\times10^{L-i}$

3.  $X-\bar{X}=D$

1,2번 식을 3번 식에 대입하여 정리하면 다음과 같은 식을 얻을 수 있다.

$$\sum_{i=0}^{\lfloor L/2\rfloor}(a_{L-i-1}-a_{i})\times10^{i}\times(10^{L-2i}-1) = D$$

여기서 임의의 음이 아닌 정수 $k$에 대해 $10^k \mod 9 = 1$이라는 사실을 떠올려보자. 양변을 9로 나눈 나머지를 취해보면, 좌변은 나머지가 0이므로 $D$ 역시 9로 나눈 나머지가 0이 되어야 한다. 그렇지 않은 경우 우측과 같은 표현법이 존재하지 않아 $X$와 $\bar{X}$가 존재하지 않음을 확인할 수 있다.

다만, $D$가 9의 배수라고 항상 이러한 표현법이 존재한다고 이야기할 수는 없다. 실제로 $D$로부터 $X$를 찾는 과정에서 그 조건을 더 자세히 확인해보자.

우리는 $D$가 9의 배수임을 확인하였으므로 자연수 $D^\prime=D/9$를 얻을 수 있다. $-9\le a_{L-i-1}-a_{i}\le9$, $10^{L-2i}-1=1111....111$이므로 $D^\prime \mod 10$은 $a_{L-1}-a{0}$와 같다. 이러한 성질을 이용하여 $i$를 점점 증가시키며 $a_{L-i-1}-a_i$를 구할 수 있다. 이 값을 구했을 때 부호에 따라 적절히 처리해주면 최소의 $X$를 구할 수 있다. 모든 $i$에 대해 시행한 후에 $D$가 0이 아니라면 $X$가 존재하지 않는다는 것을 알 수 있다.

위의 모든 풀이가 정답의 길이 $L$을 알 때 사용할 수 있는 풀이이나 $L$의 범위는 굉장히 작다는 점이다. 따라서 작은 $L$부터 증가하는 순서대로 시도하여 답을 구할 수 있다.

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

ll ipow(ll a,int n){
    if(n==0)return 1;
    if(n==1)return a;
    if(n==2)return a*a;
    ll res = ipow(a*a,n/2);
    if(n%2)res *= a;
    return res;
}

ll f(ll D,int l){
    ll res = 0;
    ll Dp=D;
    for(int i=0;2*i<l;i++){
        if(D%10>0||(D%10==0&&i!=0))res += D%10*ipow(10,l-i);
        if(D%10==0&&i==0)res += ipow(10,l-i)+(l-i!=i)*ipow(10,i);
        if(D%10<0)res -= D%10*ipow(10,i);
        D-=D%10*(ipow(10,l-2*i)-1)/9;
        D/=10;
    }
    if(D)return -1;
    else return res;
}

int main(void){
    ios::sync_with_stdio(0);cin.tie(0);
    ll D;
    cin>>D;
    if(D%9){
        cout<<"-1";
        return 0;
    }
    D/=9;
    for(int i=1;i<=17;i++){
        ll r = f(D,i);
        if(r!=-1){
            cout<<r;
            return 0;
        }
    }
    cout<<"-1";
    return 0;
}

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

매겨진 난이도가 높지만 아이디어가 어려운 문제는 아니다. 다음의 필요한 사전 지식을 안다면 쉽게 해결할 수 있다.

1. 분할 정복을 이용한 거듭제곱 - 티어 올린 주범인 듯 하다. 알면 쉬움.

2. 페르마 소정리 - 페르마 소정리 자체를 알지 못해도, 거듭제곱이 mod n에서 주기성을 가진다는 사실을 이해하면 충분하다.

우선은 1, 2, 3, 4, 5, 6의 배수인지 여부가 문제 정답에 큰 기여를 한다는 사실은 자명하다. 따라서 이들의 최소공배수를 구하자면 60이다. 이 60을 주기로 하여 반복된 패턴이 나타남을 예상할 수 있다. 필자는 최소공배수를 120으로 착각하여 풀이하였으나, 충분히 작은 공배수라면 어떤 것을 사용하여도 무관하다. 후술할 풀이에서는 주기를 120으로 사용한다.

120을 주기로 답에 포함이 되는 수인지 여부가 반복된다는 사실을 관찰하였다. 따라서 문제에서 제시된 $10^n$ 미만의 자연수 또는 0에 과연 몇 개의 주기가 들어가는지 확인하기 위하여 $10^n$을 120으로 나누어보자. $n$의 값이 1, 2, 3,...이 됨에 따라 $10^n$은 $120\times0+1,120\times0+10,120\times0+100,120\times8+40,120\times83+40,...$으로 표현됨을 확인할 수 있다.

즉, $n$이 3 이상이면 $10^n \mod 120 = 40$이 성립한다는 뜻이다. 이를 수학적 귀납법으로 증명할 수 있다. $10^n=120x+40$을 만족하는 정수 $x$가 존재한다고 가정하자. 이때 $10^{n+1}=10\times(120x+40)=1200x+400=120\times(10x+3)+40$이므로, $10^{n+1}$ 역시 120으로 나눈 나머지가 40이다. $n=3$일 때부터 해당 가정이 성립하므로 수학적 귀납법에 의하여 $n$이 3 이상일 때 $10^n \mod 120$은 40이다.

또 한 가지 위의 과정에서 관찰할 수 있는 사실은, $10^n$을 120으로 나눈 몫이 $a_n$이라 할 때, $a_{n+1}=10a_n+3$이 성립한다는 사실이다. 만약 $a_n$을 구할 수 있다면 0 이상 120 미만의 정수 중 입력 조건을 만족하는 정수의 수 $s$, 0 이상 40 미만의 정수 중 입력 조건을 만족하는 정수의 수 $t$에 대하여 정답은 $s\times a_n+t$임을 쉽게 알 수 있다. 이러한 논리 흐름을 풀이에 적용하기 위하여 $a_n$을 빠르게 구해야 하며 이는 행렬 곱셈을 활용하여 해결 가능하다.

$a_{n+1}=10a_n+3$ 꼴의 점화식을 계산하는 것은 다음 식을 통해서도 가능하다. 성립 여부는 우변을 직접 계산하면 점화식에 의해 좌변과 같이 정리할 수 있음을 통해 확인할 수 있다.

$$\begin{bmatrix}a_{n+1} \\1\end{bmatrix} = \begin{bmatrix}10 & 3 \\0 & 1\end{bmatrix}\times\begin{bmatrix}a_{n} \\1\end{bmatrix}$$

따라서 다음과 같이 행렬 거듭제곱에 관한 식으로 표현하면 분할 정복을 활용하여 쉽게 4 이상의 $n$에 대해 $a_n$을 계산할 수 있다.

$$\begin{bmatrix}a_{n} \\1\end{bmatrix} = \begin{bmatrix}10 & 3 \\0 & 1\end{bmatrix}^{n-3}\times\begin{bmatrix}a_{3} \\1\end{bmatrix}$$

이후에는 위에서 서술한 바와 같이 $s\times a_n+t$를 출력하면 된다. 더불어 해당 풀이는 $n$이 4 이상일 때 구현하기 쉬우므로, $n$이 3 이하일 때는 brute force를 활용하여 답을 구하도록 하면 깔끔하게 문제를 해결할 수 있다.

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

const ll MOD = 1000000007;

ll ipow(ll a,ll n,const int mod){
    if(n==1)return a;
    if(n==2)return 1ll*a*a%mod;
    ll res=ipow(a*a%mod,n/2,mod);
    if(n%2)res=res*a%mod;
    return res;
}

struct matrix{
    ll a,b;
    ll c,d;
    matrix operator*(const matrix t){
        return {(a*t.a%MOD+b*t.c%MOD)%MOD,(a*t.b%MOD+b*t.d%MOD)%MOD,(c*t.a%MOD+d*t.c%MOD)%MOD,(c*t.b%MOD+d*t.d%MOD)%MOD};
    }
};

matrix mpow(matrix a,ll n){
    if(n==0)return {1,0,0,1};
    if(n==1)return a;
    if(n==2)return a*a;
    matrix r=mpow(a*a,n/2);
    if(n%2)r=r*a;
    return r;
}

void tc(){
    ll n;
    scanf("%lld",&n);
    if(n<=3){
        int x[7];
        for(int i=1;i<=6;i++){
            scanf("%1d",&x[i]);
        }
        int cnt=0;
        for(int i=0;i<(n==1?10:(n==2?100:1000));i++){
            int c=0;
            for(int j=1;j<=6;j++){
                c+=((x[j]==0&&i%j!=0)||(x[j]==1&&i%j==0)||(x[j]==2));
            }
            cnt+=(c==6);
        }
        printf("%d\n",cnt);
        return;
    }
    int arr[120]={1,};
    for(int i=0;i<120;i++)arr[i]=1;
    for(int i=1;i<=6;i++){
        int x;
        scanf("%1d",&x);
        if(x==0){
            for(int j=0;j<120;j++)if(j%i==0)arr[j]=0;
        }
        if(x==1){
            for(int j=0;j<120;j++)if(j%i!=0)arr[j]=0;
        }
    }
    matrix m = mpow({10,3,0,1},n-3);
    ll r = (m.a*8+m.b)%MOD;
    ll x1=0, x2=0;
    for(int i=0;i<120;i++){
        x1+=arr[i];
    }
    for(int i=0;i<40;i++){
        x2+=arr[i];
    }
    printf("%lld\n",(x1*r%MOD+x2)%MOD);
}

int32_t main(void){
    int TC;
    scanf("%d",&TC);
    while(TC--){
        tc();
    }
}

이번 포스트는 암호학을 배우면서 간단하게 접한 확률에 관한 몇 가지 지식을 소개하고자 한다.

1. Birthday Paradox

Birthday Paradox, 즉 생일의 역설은 이후 소개드릴 내용에 비해 잘 알려져 있는 사실이다. 이는 "23명이 모여있으면 그 중 생일이 같은 두 사람이 존재할 확률이 약 50%이다"라는 내용으로 흔히 소개되어 처음 접하면 "생각보다 많이 적네?" 싶은, 조금은 신기한 사실이다.

CTF에서는 몇 가지의 분류가 존재하는 값을 출력하는 확률적 알고리즘에 대해 같은 분류에 속하는 두 가지 출력을 얻고자 할 때 종종 사용된다. md5 해시의 값을 정수로 바꾸어 65537로 나눈 나머지가 같은 두 원본 텍스트 쌍을 찾는 경우 같은 예시가 존재한다.

물론 확률에 기반한 시행이므로 평균적으로 빨리 시행됨을 알려주는 것이므로 시행 시간에는 편차가 존재할 수 있다.

• Recommend to read : 위키백과 - 생일 공격

2. Frequency of Prime number

$x$ 이하의 소수의 개수를 의미하는 소수 계량 함수 $\pi(x)$에 대해 $\displaystyle\lim_{x\rightarrow\infty} \frac{\pi(x)}{x/\ln x}=1$이 성립한다.

이는 Big-Theta notation의 정의 $f(x)\in \Theta(g(x)) \Leftrightarrow 0<\displaystyle\lim_{x\rightarrow\infty} \frac{f(x)}{g(x)}<\infty$에 따라 $\pi(x)\in \Theta(x/\ln x)$라는 의미이기도 하며, $x$ 이하의 수를 랜덤하게 골랐을 때 그 수가 소수일 확률이 $\frac{\pi(x)}{x}\approx\frac{x/\ln x}{x}=\frac{1}{\ln x}$임을 의미하기도 한다.

CTF에서는 $n$-bit 정수를 랜덤하게 뽑을 때 소수일 확률이 $1/n$이며, 따라서 uniform하거나 그렇다고 추정되는 $n$-bit number generator을 반복 실행하여 소수를 얻을 실행 횟수의 기댓값이 $n$임을 알려주어 brute force 풀이의 근거가 된다.

대표적인 사용 예시로는 소수인 MD5 해시값을 찾는 경우가 있다. MD5는 32byte=256bit를 출력하는 해시 알고리즘이므로 평균적으로 $\ln{255}\approx177$개의 해시값을 구하면 소수인 MD5 해시값을 얻을 수 있다.

• Recommend to read : 위키백과 - 소수 계량 함수

3. Probablity of $\gcd(n,m)=1$

임의의 두 자연수 $n,m$에 대해 두 수가 서로소일 확률을 $P$라고 하자. 임의의 두 자연수의 최대공약수가 $d$일 확률을 $P(d)$라고 하자. 이때, 임의의 두 자연수는 자연수인 최대공약수를 가지므로 $\displaystyle\sum_{d=1}^{\infty} P(d) = 1$이 성립한다.

또한 어떤 두 자연수 $n,m$의 최대공약수가 $d$라 하면 $gcd(n/d,m/d)=1$이다. 바꿔말하자면 두 서로소인 자연수 $a,b$를 이용하여 $da,db$라는 최대공약수가 $d$인 두 자연수 쌍을 만들 수 있다. 임의의 자연수를 고를 때 $d$의 배수일 확률은 $1/d$이므로 $P(d)=P\times(1/d)\times(1/d)=P/d^2$이다.

즉, $\displaystyle\sum_{d=1}^{\infty} P(d) = \sum_{d=1}^{\infty} P/d^2 = P\times\sum_{d=1}^{\infty} 1/d^2 = \frac{\pi^2}{6}P = 1$이다. 따라서 $P=\displaystyle\frac{6}{\pi^2}$이다.