[C++] 7881번 YAPTCHA

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

---

 

25/10/27

 

 

윌슨 정리를 알아야 하는 문제이다.

---

 

문제 접근 방식:

 

 

$$S_{n} =\sum _{ k=1 }^{ n }{ \left\lfloor \frac{(3k+6)!+1}{3k+7}- \left\lfloor  \frac{(3k+6)!}{3k+7}\right\rfloor  \right\rfloor}$$

편의 상 $3k+7$을 $m$이라고 두자.

$$S_{n} = \sum_{k=1}^{n}\left\lfloor \frac{(m-1)!+1}{m} - \left\lfloor \frac{(m-1)!}{m} \right\rfloor  \right\rfloor$$

$(m-1)! = pm+q, \ (0 \leq q < m)$라고 하자.

$$\begin{align}S_{n} &= \sum_{k=1}^{n}\left\lfloor \frac{pm+q+1}{m} - p  \right\rfloor \\ &= \sum_{k=1}^{n}\left\lfloor \frac{q+1}{m} \right\rfloor  \\ \end{align}$$

즉, $q = m-1$일 때, 안의 항이 $1$이 되고, 그 외의 경우 $0$이 된다.

$$\begin{align}q=m-1 &\iff (m-1)! - pm = m-1 \\ &\iff (m-1)! = -1 \ (\text{mod }m) \\ \text{(by Wilson's Theorem)}&\iff m \text{ is prime}\end{align}$$

윌슨 정리에 의하여 이는 $m$이 소수라는 조건과 동치이므로, $3k+7$이 소수인지 아닌지 판단하여 이전 값에 $1$을 더하던지 더하지 않던지 판단하면 된다.

---

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

// 7881번 YAPTCHA
// 정수론, 에라토스테네스의 체
#include <iostream>
#include <vector>

using namespace std;
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'

int main(void){
    fastio

    vector<int> sieve(3'000'100, 1);
    sieve[0] = 0; sieve[1] = 0;
    for (int i = 2; i*i < 3'000'100; ++i){
        if (sieve[i]){
            for (int j = i*i; j < 3'000'100; j += i){
                sieve[j] = 0;
            }
        }
    }
    vector<int> accum(1'000'001, 0);
    for (int i = 1; i < 1'000'001; ++i){
        if (sieve[3*i+7]){
            accum[i] = accum[i-1] + 1;
        }
        else{
            accum[i] = accum[i-1];
        }
    }
    int T; cin >> T;
    int n;
    while (T--){
        cin >> n;
        cout << accum[n] << endl;
    }
    return 0;
}