SNUPS PS-INTRO 4주차 풀이 (1)

SNUPS에서 나랑 Coffeetea가 같이 PS를 처음 시작하는 사람들을 위한 스터디를 진행하고 있는데,

앞으로는 이 블로그에 내 문제 설명 능력/깔끔하고 알아보기 쉽게 코딩하는것도 연습할겸 해서 풀이를 올려보려고 한다.

 

이번 주차 주제는 PS를 위한 기초적인 수학으로 준비되었다. 

---

2609. 최대공약수와 최소공배수

단순 구현 문항. 유클리드 호제법을 직접 구현하던가, 귀찮다면 그냥 GCC 내장 함수를 쓰자.

물론 MS C++에는 아마 없는 함수인걸로 알고있지만... 99%의 대회는 GCC니까.

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

int main()
{
    int a, b;
    scanf("%d %d",&a,&b);
    int g = __gcd(a,b);
    printf("%d\n%d",g,a*b/g);
}

---

1929. 소수 구하기

에라토스테네스의 체를 구현한 다음, 적당히 $m$부터 $n$까지 돌면서 소수가 몇개인지 세주면 된다.

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

bool is_composite[1020000];
int main()
{
    int m,n;
    scanf("%d %d",&m,&n);
    is_composite[1] = 1;
    for (int i = 2; i<1020000; i++)
    {
        if(!is_composite[i])
        {
            for (int j = 2*i; j<1020000; j+=i)
                is_composite[j] = 1;
        }
    }
    for (int i = m; i<=n; i++)
        !is_composite[i]?printf("%d\n",i):1;
}

---

4948. 베르트랑 공준

엄청나게 유명한 정리인 베르트랑 공준에 대한 문제이다. 저 정리는 언젠가 정수론 공부할때 다시 포스팅 할것 같은데..

아무튼, 이 문제의 경우 단순하게 $n < p \leq 2n$ 인 소수 $p$ 의 개수를 구하는 문제이다.

 

어떤 주어진 구간에서 개수를 구하는 매우 좋은 방법 중 하나는, 처음부터 그 구간까지의 누적합을 저장하는 것이다. 

앞 문제에서 작성한 에라토스테네스의 체 코드를 활용, 누적합 배열 $arr[i]$ 를 다음과 같이 정의하자.

\[arr [i] := \text{number of primes less or equal than } i \]

이제, 우리가 원하는 답은 $arr[2n] - arr[n]$ 을 해주면 된다.

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

int arr[250000];
bool is_composite[250000];
int main()
{
    is_composite[1] = 1;
    for (int i = 2; i<250000; i++)
    {
        if(!is_composite[i])
        {
            for (int j = 2*i; j<250000; j+=i)
                is_composite[j] = 1;
        }
    }
    for (int i = 1; i<=250000; i++)
        arr[i] = arr[i-1]+(!is_composite[i]);
    while(1)
    {
        int n;
        scanf("%d",&n);
        if (n==0)
            return 0;
        else
            printf("%d\n",arr[2*n]-arr[n]);
    }
}

---

9020. 골드바흐의 추측

약간 어려울 수 있는데...

$n = p_1 + p_2$ 로 나타낼 수 있는 두 소수 $p_1, p_2$ 를 찾는 문제이다. 주어진 수가 1만까지밖에 없기 때문에, 일단은 1만까지의 에라토스테네스 체를 돌아 주고 생각하자. 여기까지 연산횟수는 많아야 수만 번이다.

이제, 우리는 딱히 뾰족한 수가 없으니까 가능한 모든 조합을 검토하자. 

즉, 어떤 $p_1$에 대해서, $n-p_1$ 이 소수인 모든 경우의 수를 검토하겠다는 의미이다.

 

그러나, 우리는 속도가 가능한 빨랐으면 좋겠으므로, 

$p_1$을 $\frac{n}{2}$ 부터 시작해서 줄이자. 그러면, 처음 찾는 가능한 $p_1, p_2$ 조합이 가장 차가 작은 골드바흐 파티션이다.

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

int arr[250000];
bool is_composite[10100];
int main()
{
    is_composite[1] = 1;
    for (int i = 2; i<10100; i++)
    {
        if(!is_composite[i])
        {
            for (int j = 2*i; j<10100; j+=i)
                is_composite[j] = 1;
        }
    }
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        for (int i = n/2; i>1; i--)
        {
            if ((!is_composite[i]) && (!is_composite[n-i]))
            {
                printf("%d %d\n",i,n-i);
                break;
            }
        }
    }
}

이 문제를 푸는 데 어려움이 없었다면, 제한이 100배 큰 6588번을 풀고 지나가자.

---

11401. 이항 계수 3

스터디 중 다루었던 문제인데...

\[ _nC_m = \frac{n!}{m! (n-m)!} \] 임을 이용해야 한다.

 

빠른 모듈로 거듭제곱법과 페르마의 소정리를 이용하여, $(m!)^{p-2}$ 를 구해주면 $1/m!$ 를 곱하는 대신 $m!$의 모듈러 역수를 곱하는 것으로 처리하면 된다. 같은 방법으로 $(n-m)!$ 도 해결해 주면 끝.

코드는 6개월 전에 짠거라 상당히 이상한 부분이 많지만 로직을 보는데는 이상이 없어 보이니 넘어가자.

#include <bits/stdc++.h>

typedef long long int lli;
const lli Big = (lli)(int)1e9+7;

lli n,k;

lli mul(lli x, lli y, lli p) // x^y mod p
{
    lli ans = 1;
    while (y > 0)
    {
        if (y%2 != 0)
        {
            ans *= x;
            ans %= p;
        }
        x *= x;
        x %= p;
        y/=2;
    }
    return ans;
}

int main()
{
    lli A=1,B=1,C=1;
    scanf("%lld %lld",&n,&k);
    for (int i = 1; i<=n; i++)
    {
        A *= i;
        A %= Big;
    }
    for (int i = 1; i<=(n-k); i++)
    {
        B *= i;
        B %= Big;
    }
    B = mul(B,Big-2,Big);
    for (int i = 1; i<=k; i++)
    {
        C *= i;
        C %= Big;
    }
    C = mul(C,Big-2,Big);
    printf("%lld",((((A*B)%Big)*C)%Big));
}

지금은 long long의 abbreviation으로 ll을 쓰고, 대부분의 PS러들이 그러긴 하는데

저때는 왜인지 lli를 썼었다. long long int라서? ㅋㅋㅋㅋ

그리고 왜 함수이름을 mul이라고 지었는지도 기억이 안난다. modular multiplicative inverse 일텐데, modinv나 modexp가 훨씬 직관적이고 좋은거 같은데.