문제 풀이/AtCoder

[AtCoder - ABC212 G] Power Pair

hibye1217 2023. 3. 4. 22:26

난이도: 2150

 

태그

더보기
  • Number Theory
    • Primitive Root 
    • Prime Factorizations, Divisors
    • Fermat's Little Theorem
    • Modular Multiplicative Inverse
    • Greatest Common Divisor
    • + Highly Composite Number
  • Combinatorics

 

풀이

1. 소수 모듈러가 가지는 특징을 생각해보자.

더보기

소수 모듈러는 다양한 특징을 가지고 있습니다.

 

이 중에서 이번에 저희들이 사용할 건 아래와 같습니다.

  • 모든 소수 \( P \)는 적어도 하나 이상의 원시근 \( G \)를 가진다.

 

// 원시근이 뭔지 모르는 사람들을 위해:

// 소수 \( P \)의 원시근은 \( G^1, G^2, G^3, \ldots, G^{P-1} \)이 모두 다른 값을 가지게 하는 수 \( G \)를 의미합니다.

// 즉, \( 1 \)부터 \( P-1 \)까지의 모든 수를 \( G^k \text{ mod } P \)만으로 나타낼 수 있다는 거죠.

 

2. 원시근 \( G \)를 기준으로 생각해보면, \( x = G^a \)가 고정될 때 가능한 \( y = G^b \)의 경우는?

더보기

사실 이 전에 하나 더 처리해야 하는 것이 있습니다. \( x = 0 \)이죠.

\( x = 0 \)일 때는 \( x^n = 0 \)이기 때문에, \( y = 0 \)인 경우만 가능합니다.

 

앞으로는 \( x \ge 1 \)이라고 가정하겠습니다.

 

\( x = G^a \)와 \( y = G^b \)에 대해 \( x^n = y \pmod P \)라는 건, \( G^{an} = G^b \pmod P \)를 의미합니다.

이는, 페르마의 소정리에 의해 \( an = b \pmod {P-1} \)을 의미하죠.

 

\( an = b \pmod {P-1} \)를 만족시킬 수 있는 \( b \)는 총 \( \frac{P-1}{\gcd(P-1, a)} \)개입니다.

// 가능한 P-1개의 수 중, \( \gcd(P-1, a) \)의 배수가 아닌 수는 도달할 수 없으니 제외한 결과입니다.

 

이제 \( a \)에 대해 가능한 \( b \)의 개수를 구했지만... \( a \)의 범위 자체도 매우 크므로

아무래도 \( a \)에 대해서도 무언가 작업을 해놓아야 할 것 같아 보입니다.

 

3. \( g = \gcd(P-1, a) \)를 정확히 만족시키는 \( a \)의 개수는?

더보기

\( P-1 \)의 소인수분해 \( p_1^{e_1} \cdot p_2^{e_2} \cdot \ldots \cdot p_k^{e^k} \)를 생각해봅시다.

\( g \)는 \( P-1 \)의 약수이기 때문에, \( g \)의 소인수분해는 \( 0 \le d_i \le e_i \)인 \( d_i \)에 대해

\( p_1^{d_1} \cdot p_2^{d_2} \cdot \ldots \cdot p_k^{d^k} \)으로 나타낼 수 있습니다.

 

이제, 이를 토대로 \( g \)를 고정시킬 때 가능한 \( a \)를 생각해봅시다.

\( a \)의 소인수분해 속 하나의 항 \( p^e \)에 대해:

  • 만약 \( p \)가 \( p_i \)와 겹치지 않는다면?
    지수 \( e \)는 무슨 값이든 상관 없습니다. 어차피 GCD 하면 날아갈 항이니까요.
  • 만약 \( p \)가 \( p_i \)와 겹친다면?
    • 만약 \( d_i = e_i \)라면?
      지수 \( e \)를 \( d_i \)회 이상 사용해야 합니다.
    • 만약 \( d_i < e_i \)라면?
      지수 \( e \)를 정확히 \( d_i \)회 사용해야 합니다.

 

하지만 이는 너무 복잡합니다. 그냥 배수를 세는 것도 아니고, 특정한 소수들을 사용할 수 있는 횟수가 정해져 있는 상태에서의 (게다가 그 와중에 몇몇개는 하한만 정해져있는 상태의) 배수를 세야 하기 때문이죠.

 

4. [3]의 약화 버전을 생각해보자. \( g \)를 고정시킬 때, \( g | \gcd(P-1, a) \)인 \( a \)의 개수는?

더보기

이건 쉽습니다. 정의상 \( P-1 \)은 \( g \)의 배수이므로, \( a \)가 \( g \)의 배수이기만 하면 되기 때문입니다.

즉, 이 때 가능한 경우는 \( \frac{P-1}{a} \)가지가 됩니다.

앞으로는 이 값을 \( C_{g} \)라고 부르겠습니다.

 

5. \( \gcd(P-1, a) \)로 가능한 수는 몇 개일까? 이를 토대로, 질문 [3]에 답할 방법을 찾을 수 있을까?

더보기

뜬금없어보이지만, Highly Composite Number에 대해 생각해봅시다.

\( N \)이 Highly Composite Number라는 건, \( N < M \)인 모든 \( M \)에 대해 (\( M \)의 약수 개수) < (\( N \)의 약수 개수)임을 의미합니다.

\( 10^{12} \) 이상의 첫 Highly Composite Number는 \( 1\,124\,388\,064\,800 \)이고, 이 수의 약수는 \( 7\,000 \)개도 되지 않습니다.

즉, Highly Composite Number의 정의에 따라 \( 10^{12} \) 이하의 모든 수는 약수가 \( 7\,000 \)개도 되지 않습니다.

 

이는 \( g = \gcd(P-1, a) \)로 가능한 수 역시 \( 7\,000 \)개 이하임을 의미합니다.

그러므로, \( g \)가 큰 수부터 시작해서 \( C_{g} \) -= \( C_{g'} \text{ where } g|g' \)를 계산해주면 됩니다.

// \( g \)의 배수까지 다 포함한 값을 [4]에서 계산한 뒤,

// [5]에서는 \( g \)가 아닌 \( g \)의 배수를 제거한다고 생각하면 됩니다.

 

6. 그런데 이거 왜 구했더라?

더보기

\( b \)의 개수를 구하는데 있어서, \( g = \gcd(P-1, a) \)가 동일하다면 \( a \)의 값 자체는 큰 상관이 없기 때문입니다.

// 개수의 식 \( \frac{P-1}{\gcd(P-1, a)} \)을 다시 생각해봅시다.

 

즉, \( g \)에 대해 돌리면서 가능한 \( a \)의 개수 × 가능한 \( b \)의 개수를 더해 출력하면 된다는 것을 의미합니다.

수식으로 쓰자면, \( C_{g} \times \frac{P-1}{g} \)이 되겠죠.

 

7. 구현할 때 주의할 점

더보기

Modular가 \( 998\,244\,353 \)인데, 귀찮게도 분모에도 \( 998\,244\,353 \)의 배수가 들어갈 수 있습니다.

대신에, 분모에 \( 998\,244\,353^2 \)는 들어갈 수 없으니 + 분모에 \( 998\,244\,353 \)의 배수가 들어간다면 분자에도 \( 998\,244\,353 \)의 배수가 들어가니

분모가 \( 998\,244\,353 \)의 배수라면 분모랑 분자를 \( 998\,244\,353 \)으로 나눈 뒤 계산하면 됩니다.

 

이 부분이 필요한 이유는, Modular 위에서 분수를 들고 있는 건 어렵기 때문에 분모의 모듈러 곱셈 역원을 곱하는 방식을 사용할텐데, 만약 분모가 Modular의 배수라면 모듈러 곱셈 역원이 존재하지 않기 때문입니다.

 

8. 코드

더보기
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
const ll mod = 998244353;
ll fpow(ll mul, ll bit){ ll res = 1;
    mul %= mod;
    while (bit){
        if (bit&1){ res = res*mul % mod; }
        mul = mul*mul % mod; bit >>= 1;
    }
    return res;
}
inline ll finv(ll x){ return fpow(x, mod-2); }
 
map<ll, ll> mp;
 
void Main(){
    ll n; cin >> n; n -= 1;
    for (ll p = 1; p*p <= n; p++){
        if (n%p == 0){ mp[p] = n/p; mp[n/p] = p; }
    }
    for (auto it = mp.rbegin(); it != mp.rend(); it++){
        for (auto jt = mp.rbegin(); jt != it; jt++){
            if ((*jt).fr % (*it).fr != 0){ continue; }
            (*it).sc -= (*jt).sc;
        }
    }
    ll ans = 1;
    for (pl2 p : mp){
        ll g = p.fr, c = p.sc; c %= mod;
        //cout << "COUNT " << g << ' ' << c << endl;
        if (g%mod == 0){ ans += n/mod %mod *c %mod *finv(g/mod) %mod; }
        else{ ans += n %mod *c %mod *finv(g) %mod; }
        ans %= mod;
    }
    cout << ans;
}
 cs