[C++] 7118번 Ones

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

---

 

25/02/26

 

 

예전에 문제를 보고 잘 안풀려서 북마크에 넣어두고 나중에 풀어봐야지 했던 문제인데, 오랜만에 다시 꺼내서 태그를 까고 해결했다.

 

지수승강 보조정리(LTE Lemma)의 기초를 배울 수 있었던 좋은 문제였다.

---

 

문제 접근 방식:

 

 

문제는 다음과 같다.

 

$a = \underbrace{111 \ \dots \ 111_{(t)}}_{n}$ $n$개의 $1$로 구성된 $t$진수로 표현된 수 $a$가 주어진다고 하자.

이때, $2^{u}, 3^{v}$가 각각 $a$를 나눈다고 하면 그때의 $u$와 $v$의 최댓값을 구하자.

 

$t$와 $n$의 제한은 각각 $10^9$임을 생각해보면, 나이브하게 곱하면 숫자가 너무 커질 것이라는 생각이 들 것이다.

 

 

이때, LTE Lemma는 p-adic valuation $\nu_{p}(n)$를 계산하는 공식을 제공한다. (여기서 $p$는 소수이다.)

 

그러면 p-adic valuation(다른 말로 p-adic order) $\nu_{p}$는 뭘까?

 

$n$의 p-adic valuation $\nu_{p}(n)$은 $p^{k}$가 $n$을 나눌 때 가능한 가장 큰 정수 $k$값으로 정의된다.

 

즉, 쉽게 말하자면 어떤 수 $n$이 가지고 있는 소인수 $p$의 개수라고 보면 된다. 위에서 이야기 한것과 동일한 말이다.

 

 

즉, 위의 문제를 위의 표기법으로 표현하면 $\nu_{2}(a), \nu_{3}(a)$의 값을 구하는 것이 목표가 된다.

 

다시 말하면, $a$를 소인수 분해 하였을 때 가지는 소인수 $2$와 $3$의 개수를 구하는 것이 우리의 목표이다.

 

https://en.wikipedia.org/wiki/Lifting-the-exponent_lemma

Lifting-the-exponent lemma - Wikipedia

위키를 참고하여 내용을 작성했다.

 

LTE Lemma의 기본 전제는 $p$가 소수이고, 그 $p$가 $x$와 $y$를 각각 나누지 않을때가 기본 전제다.

즉, $p \nmid x, p \nmid y$가 기본 전제이다. 이를 상기시키면서 뒤의 내용을 읽어보자.

 

1. $\nu_{2}(a)$ 구하기

 

이때, LTE Lemma는 다음과 같은 내용을 이야기 해준다.

 

$p = 2$인 경우,

$p \mid x-y$이고 $2 \mid n$일 때 $\nu_{p}(x^{n} - y^{n}) = \nu_{p}(x-y) + \nu_{p}(x+y) + \nu_{p}(n) - 1$이다.

$p \mid x-y$이고 $2 \nmid n$일 때 $\nu_{p}(x^{n} - y^{n}) = \nu_{p}(x-y)$이다.

 

즉, 다시 쓰자면,

$2 \mid x-y$이고 $2 \mid n$일 때 $\nu_{2}(x^{n} - y^{n}) = \nu_{2}(x-y) + \nu_{2}(x+y) + \nu_{2}(n) - 1$이다.

$2 \mid x-y$이고 $2 \nmid n$일 때 $\nu_{2}(x^{n} - y^{n}) = \nu_{2}(x-y)$이다.

 

우리는 $a = 111 \ \dots \ 111_{(t)} = t^{n-1} + t^{n-2} + \cdots + t + 1 = (t^{n} - 1) / (t - 1)$이라는 사실을 잘 알고있다.

 

그리고 $t^{n} - 1$은 위에서 이야기 한 LTE Lemma의 Statement에서 나온 식의 형태이다!

 

그러니까, $\nu_{2}(t^{n} - 1)$의 값을 구해보고, 이를 통해 $a$의 값을 찾아내면 될 것 같다는 생각이 자연스럽게 들 것이다.

 

$\nu_{p}(n)$의 정의를 상기시켜보자. 어떤 정수 $n$이 가지고 있는 소인수 $p$의 개수가 $\nu_{p}(n)$이었다.

 

이에 따르면, $\nu_{2}(t^{n} -1) = \nu_{2}(a\cdot (t-1))$은 $t^{n} -1 = a \cdot (t-1)$이 가지고 있는 소인수 $2$의 개수이고, 이는 $a$가 가지고 있는 소인수 $2$의 개수와 $t-1$이 가지고 있는 소인수 $2$의 개수의 합과 같다.

성질: $\nu_{p}(a \cdot b) = \nu_{p}(a) + \nu_{p}(b)$

 

즉, 다시 말하자면  $\nu_{2}(t^{n} - 1)$의 값을 LTE Lemma로 구하고, $\nu_{2}(t-1)$의 값($t-1$은 $10^9$보다 작기 때문에 일일히 $2$로 나눠봄으로써 구할 수 있다!)을 그냥 구한 뒤, 두 값을 빼주면 $\nu_{2}(a)$의 값이 나올 것 같다는 생각이 든다.

 

그러면 실제로 $\nu_{2}(t^{n} - 1)$의 값을 LTE Lemma로 구할 수 있는지 생각해보자.

 

1-1. $t$가 홀수라면

 

$t-1$은 항상 $2$로 나눠진다. 또한 $2 \nmid t$, $2 \nmid 1$이다. 따라서 LTE Lemma의 조건을 만족한다.

 

$$\begin{align} \nu_{2}(t^{n} - 1) &= \nu_{2}(t^{n} - 1^{n}) \\ &= \nu_{2}(t-1) + \nu_{2}(t+1) + \nu_{2}(n) - 1 \text{ if n is even} \\ &\ \ \ \ \ \nu_{2}(t-1) \text{ if n is odd}\end{align}$$

 

여기에 $\nu_{2}(t-1)$의 값을 각각 빼주면,

 

$$\begin{align} \nu_{2}(a) &= \nu_{2}(t+1) + \nu_{2}(n) - 1 \text{ if n is even} \\ &\ \ \ \ \ 0 \text{ if n is odd}\end{align}$$

 

이 된다.

 

1-2. $t$가 짝수라면

 

$2 \mid t$이기 때문에 LTE Lemma를 적용할 수 없다.

 

하지만 상관 없다!

 

$a = t^{n-1} + t^{n-1} + \cdots + t + 1$이기 때문에 이 경우 $a$는 항상 홀수임이 확인된다. 따라서 $a$가 가지고 있는 소인수 $2$의 개수는 항상 $0$이다. 따라서 이 경우 $\nu_{2}(a) = 0$이 된다.

 

 

2. $\nu_{3}(a)$ 구하기

 

$p = \text{odd}$인 경우 LTE Lemma는 다음과 같은 내용을 이야기 해주고 있다.

 

$p \mid x-y$일 때, $\nu_{p}(x^{n} - y^{n}) = \nu_{p}(x-y) + \nu_{p}(n)$

$p \mid x+y$이고 $2 \nmid n$일 때, $\nu_{p}(x^{n} + y^{n}) = \nu_{p}(x+y) + \nu_{p}(n)$

$p \mid x+y$이고 $2 \mid n$일 때, $\nu_{p}(x^{n} + y^{n}) = 0$

 

LTE Lemma의 전제 조건은 $p \nmid x, p \nmid y$일 때라는 사실을 항상 유념하자.

 

2-1. $t = 3k+1$인 경우

 

위에서 했던 것과 비슷하다. $t-1$은 항상 $3$으로 나눠진다. 또한, $3 \nmid t, 3 \nmid 1$이다. 따라서 LTE Lemma를 사용할 수 있다.

 

따라서, $\nu_{3}(t^{n} - 1) = \nu_{3}(t-1) + \nu_{3}(n)$이다.

 

우리가 구하는 것은 $\nu_{3}(a)$이므로 $\nu_{3}(t-1)$의 값을 빼주면, $\nu_{3}(a) = \nu_{3}(n)$이 된다.

 

2-2. $t = 3k$인 경우

 

$t-1$은 $3$으로 나눠지지 않기 때문에 LTE Lemma를 적용할 수 없다.

 

하지만 $a = t^{n-1} + t^{n-2} + \cdots + t + 1$이기 때문에 $3$의 배수에 1을 더한 형태고, $a$는 $3$으로 나눠지지 않는다.

 

따라서 이 경우 $\nu_{3}(a) = 0$이 된다.

 

2-3. $t = 3k+2$인 경우

 

$\nu_{3}(a) = \nu_{3}(t^{n}-1) - \nu_{3}(t-1)$을 구하자.

 

1. 먼저, $\nu_{3}(t^n - 1)$을 구해야 하는데, LTE Lemma는 적용할 수 없다. ($\because 3 \nmid (3k + 2 - 1)$)

 

그러면 $(3k+2)^n - 1$이 가지는 최대 $3$의 개수를 Lemma없이 구해봐야 한다.

 

2. $\mod 3$을 씌워서 생각해보자.

 

만약 $2^{n} - 1 (\text{mod }3) \neq 0$이라면 $3$으로 안나눠 떨어진다는 뜻이므로 $\nu_{3}(t^n - 1) = 0$이다.

 

즉, $2^n (\text{mod }3) \neq 1$이라면 $\nu_{3}(t^n - 1) = 0$이 된다.

 

$n$을 하나씩 늘려가며 확인해보면 $n$이 홀수일 때는 $2^n (\text{mod }3) = 2$, $n$이 짝수일 때는 $2^n (\text{mod }3) = 1$임을 확인할 수 있다. (유식한 말로 $\mathbb{Z}_{3}^{\times}$에서의 $2$의 order는 $2$이다.)

 

따라서, $n$이 홀수일 때는 $\nu_{3}(t^{n} - 1) = 0$이고, $n$이 짝수일 때는 $\nu_{3}(t^{n} - 1) \geq 1$이다.

 

3. $n$이 짝수라면, 다시 말해 $n = 2m$이라면,

$\nu_{3}(t^n - 1) = \nu_{3}(t^{2m} - 1) = \nu_{3}((t^m-1)\cdot(t^m +1)) = \nu_{3}(t^m - 1) + \nu_{3}(t^m + 1)$이다.

 

근데 $\nu_{3}(t^m + 1)$은 LTE Lemma를 적용할 수 있다!($\because 3 \mid (3k+2 + 1)$)

 

그리고 그 값은 $m$이 짝수라면 $0$, 홀수라면 $\nu_{3}(t+1) + \nu_{3}(m)$이다.

 

하지만 $\nu_{3}(t^m - 1)$은 여전히 LTE Lemma로 구하지 못한다. 이 상황은 위의 1번 상황과 매우 유사하다!

 

따라서 1번 과정으로 돌아가서 다시 재귀적으로 적용하면 된다. 이 상황해서 이미 구했던 값, 예를 들어 $\nu_{3}(t+1)$과 같은 값을 여러 번 중복해서 구할 수도 있으니, 메모이제이션을 해가며 구하면 된다.

---

아래는 내가 위의 접근 방식과 같이 작성한 C++ 코드이다. 더보기를 누르면 확인할 수 있다.

// 7118번 Ones
// LTE Lemma
/*
문제:
a = 111 ... 11_(t) n개의 1로 구성된 t진수로 표현된 a가 있다
즉, a = t^{n-1} + t^{n-2} + ... + t + 1 = (t^n - 1) / (t - 1)이다.

구하는 값:
2^u, 3^v가 각각 a를 나눌 경우, 그때의 u와 v의 최댓값 구하기.

- LTE Lemma
p-adic valuation v_p를 계산하는 공식을 제공함.
What is p-adic valuation(p-adic order) v_p?
p-adic valuation of n v_p(n) := p^k|n일때 가장 큰 k값

즉, 위의 경우 v_2(a), v_3(a)의 값을 구하는 것이 목표임.

- v_2(a) 구하기:
p = 2인 경우 다음과 같은 사실이 알려짐.
전제 조건: 2/|x && 2/|y
2|x-y이고 n이 짝수일 때: v_2(x^n - y^n) = v_2(x-y) + v_2(x+y) + v_2(n) - 1
2|x-y이고 n이 홀수일 때: v_2(x^n - y^n) = v_2(x-y)

-- t가 홀수라면
t-1은 항상 2로 나눠진다. 그리고 2/|t, 2/|1조건도 만족시킨다.
b = a*(t-1) = t^n - 1 = t^n - 1^n이라고 하자. 
즉, LTE렘마를 사용할 조건이 된다.
v_2(a*(t-1)) = v_2(b) 
= v_2(t^n - 1^n) 
= v_2(t-1) + v_2(t+1) + v_2(n) - 1 (n is even) or v_2(t-1) (n is odd)

우리가 구하는건 v_2(a)이므로, t-1을 곱해줌으로써 더해진 소인수 2의 개수만큼 빼주면 된다.
그러면 케이스가 더 간단해진다.
즉, v_2(a) = v_2(t+1) + v_2(n) - 1 (n is even) or 0(n is odd)

-- t가 만약 짝수라면
2|t이기 때문에 LTE Lemma를 적용할 수 없다. 근데 상관 없다.
a = t^{n-1} + t^{n-2} + t^{n-3} + ... + 1
짝수끼리 더하다 1을 더했기 때문에 0이다.

- v_3(a) 구하기:
p = odd인 경우 다음과 같은 사실이 알려짐.
전제 조건: p/|x && p/|y
p|x-y일 때: v_p(x^n - y^n) = v_p(x-y) + v_p(n)
p|x+y이고 n이 홀수일 때: v_p(x^n + y^n) = v_p(x+y) + v_p(n)
p|x+y이고 n이 짝수일 때: v_p(x^n + y^n) = 0

-- t가 3k+1인 경우
t-1은 항상 3으로 나눠진다. 그리고 3/|t, 3/|1조건도 만족시킨다.
즉, LTE렘마를 사용할 조건이 된다.
b = a*(t-1) = t^n - 1 = t^n - 1^n이라고 하자.
그러면, v_3(a*(t-1)) = v_3(b) 
= v_3(t^n - 1^n) 
= v_3(t-1) + v_3(n)

우리가 구하는건 v_3(a)이므로, t-1을 곱해줌으로써 더해진 소인수 3의 개수만큼 빼주면 된다.
그러면 케이스가 더 간단해진다. 즉, v_3(a) = v_3(n)

-- t가 3k인 경우, a = t^{n-1} + .... + t^{1} + 1이므로 v_3(a) = 0이다.

-- t가 3k+2인 경우

v_3(a) = v_3(t^n - 1) - v_3(t-1)를 구하자

1. 먼저 v_3(t^n - 1)을 구해야 한다. 
LTE Lemma는 적용할 수 없음에 유의하자. (왜냐하면 3/|(3k+2 - 1)이기 때문)

2. (3k+2)^n - 1이 가지는 최대 3의 개수를 구해야 한다.
mod 3을 씌워서 생각해보자.
2^n - 1 (mod 3) != 0이라면 3으로 안나눠진다는 뜻이므로 0이다.
즉, 2^n (mod 3) != 1이라면 3으로 안나눠진다는 뜻임.
3에서의 2의 order를 생각해보면, n이 홀수일 때는 2이므로 0이라는 사실을 알 수 있다.

3. n이 짝수라면 3으로 나눠지므로, v_3(t^n - 1) >= 1이다.
v_3(t^{2m} - 1) = v_3((t^m - 1)*(t^m + 1)) = v_3(t^m - 1) + v_3(t^m + 1)
v_3(t^m + 1)은 LTE lemma를 적용할 수 있다. (3|(3k+2 + 1)이기 때문)
그 값은 m이 짝수라면 0, m이 홀수라면 v_3(t+1) + v_3(m)이다.

v_3(t^m - 1)을 구하자. 이는 1번 과정부터 다시 반복하면 구할 수 있다.
*/
#include <iostream>
#include <map>
using namespace std;
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'

map<pair<int, int>, int> v_3_1;
map<int, int> v_3_2;
int v_p(int x, int p){
    if (p == 3 && v_3_2.find(x) != v_3_2.end()){
        return v_3_2[x];
    }
    int ans = 0;
    while (x % p == 0){
        x /= p;
        ans++;
    }
    if (p == 3){
        v_3_2[x] = ans;
    }
    return ans;
}

int case3(int t, int n){
    if (v_3_1.find({t, n}) != v_3_1.end()){
        return v_3_1[{t, n}];
    }
    if (n % 2 == 1){
        v_3_1[{t, n}] = 0;
        return v_3_1[{t, n}];
    }
    int m = n/2;
    int one, two;
    if (m % 2 == 0) two = 0;
    else two = (v_p(t+1, 3) + v_p(m, 3));
    one = case3(t, m);
    v_3_1[{t, n}] = one+two;
    return v_3_1[{t, n}];
}

int solve1(int t, int n){
    if (t % 2 == 0){
        return 0;
    }
    if (n % 2 == 1){
        return 0;
    }
    return v_p(t+1, 2) + v_p(n, 2) - 1;
}

int solve2(int t, int n){
    if (t % 3 == 1){
        return v_p(n, 3);
    }
    if (t % 3 == 0){
        return 0;
    }
    return case3(t, n) + v_p(t-1, 3);
}

int main(void){
    int t, n; cin >> t >> n;
    cout << solve1(t, n) << ' ' << solve2(t, n);
    return 0;
}