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

3문제 남았다! 

원래는 3편 안써도 될거 같았는데, 생각보다 열심히 푸시는 분들이 있어서 굉장히 기쁜 마음으로 (진심입니다 ㅋㅋㅋ) 남은 3문제를 풀어 보자.

 

마지막 3문제는 더 많은 수학을 요구하는 문제 2개와, 조금 특이한 1문제가 들어가 있다.

---

11689. GCD(n, k) = 1

매우 유명한 함수인 오일러 피 함수를 구하는 문제이다.

어떤 자연수 $N$ 에 대하여, $1 \leq x \leq N$ 인 수 중 $N$과 서로소인 자연수의 개수를 구하면 된다.

 

먼저, $N$과 서로소라는 것은, 소인수를 공유하지 않는다 라고 해석할 수 있다. 

따라서, $N$을 먼저 적당히 소인수분해해 주자.

\[ N = p_1^{e_1} p_2^{e_2} ... \]

 

이제, $p_1$ 을 공유하지 않는 수를 세 보자.

당연한 이야기지만, 공유하는 수가 정확히 $\frac{N}{p_1}$ 개이므로 공유하지 않는 수는 $N - \frac{N}{p_1}$ 개이다.  

 

이것을 모두 각각의 소인수에 대하여 반복할 수 있다.

그러나, 이렇게 하면 소인수 2개를 공유하는 케이스는 2번씩 세어지고, 3개를 공유하는 경우는 3번씩 세어지게 된다.

따라서, 포함배제의 원리를 이용하여 원소의 개수를 세 주어야 한다.

포함배제의 원리라는 것은 합집합의 원소의 개수를 세는 방법인데, 우리가 $A$, $B$, $C$ 세 집합의 합집합의 원소를 셀 때, 세 개의 합집합에서 두 개씩 합한걸 다 뺀 다음, 다시 각각을 더하는 그 원리를 $n$개의 집합으로 일반화한 것이다.

 

다만, 오일러 피 함수의 경우 훨씬 아름답고 간결한 공식이 존재한다. 그렇기 때문에, 사실은 포함배제를 직접 계산할 필요는 없다. (공식 유도 과정은 하단에 따로 제시한다.)

\[ N = p_1^{e_1} p_2^{e_2} ... \]위 형태로 나타나는 $N$에 대하여, 다음이 알려져 있다.

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

ll primecheck(ll n)
{
    ll i;
    ll condition = 1;
    if (n == 1)
        return 0;
    for (i = 2; i*i <= n; i++)
    {
        if (n%i == 0)
        {
            condition = 0;
            break;
        }
    }
    return condition;
}

int main()
{
    ll n;
    scanf("%lld",&n);
    ll on=n;
    ll p=2;
    while(p*p<=n)
    {
        if (n%p == 0)
            on = on/p * (p-1);
        while(n%p==0)
            n/=p;
        p++;
    }
    if (primecheck(n)==1)
        on = on/n * (n-1);
    printf("%lld",on);
}

---

1630. 오민식

1부터 N까지의 모든 수로 나누어 떨어지는 수, 즉 

\[ lcm (1, 2, 3, ... N) \] 을 987654321로 나눈 나머지를 구하는 문제이다.

 

단순무식하게 구현하는 방법은, 매 번 lcm을 갱신하면서 나머지 연산을 취하는 것이다.

그러나 이 방법으로는 구현이 불가능한데..

이미 어느 순간 int 범위를 벗어날 것이기 때문에 저 수로 나눈 나머지를 취해야 하는데, 나머지를 취하고 나면 lcm을 정상적으로 구할 수가 없다!

그래서, 조금 다른 방법이 필요하다.

 

 

잘 생각해 보면, 어차피 소수들 외에는 lcm에 영향을 미치지 않는다. 그러나 그냥 소수를 그대로 곱해 줄 수는 없고, 각각의 소수들에 대해서 $N$ 까지 안에 들어가는 가장 큰 제곱만큼을 해서 곱해주면 된다는 것을 어렵지 않게 알 수 있다. 

예를 들어, $N = 10$ 일 때는 10 이하의 소수들을 사용하되, 2 대신 8을, 3 대신 9를 곱해서

$8 \times 9 \times 5 \times 7 = 2520$ 으로 처리해 주면 된다. 

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

const int MOD = 987654321;
bool comp[1001000];

int main()
{
    int n;
    scanf("%d", &n);
    ll ans = 1;
    for(ll i=2; i<=n; i++)
    {
        if(comp[i])
            continue;
        ll t = i;
        while(t*i <= n)
            t*=i;
        ans *= t;
        ans %= MOD;
        for(ll j=i*i; j<=n; j+=i)
            comp[j]=true;
    }
    printf("%lld\n", ans);
    return 0;
}

---

16680. 안수빈수

$N$에 대하여 $NK$의 각 자리 수의 합이 홀수가 되게 하는 $K$를 찾는 문제.

 

"항상 존재한다" 는 사실에 조금 주목해 보자. 저걸 증명할 수 있다는 것은, "반드시 찾을 수 있는 방법" 이 존재한다는 뜻이다.

숫자가 $10^8$ 까지로 조금 크니까, 줄여서 생각해 보자. $10^4$ 정도로.

네 자리 숫자 $abcd$ 에 대하여, (곱이 아니라 각 자리 숫자가 abcd라는 의미)

$10^4$를 곱하면, 자릿수의 합이 바뀌지 않는다. ($abcd0000$)

이제, $10^4-1$을 곱해 보자. 그러면 자릿수의 합이 어떻게 될까?

$10000 - abcd = efgh$ 라고 할 때, $abc (d-1) efgh$ 가 성립할 것이다. (d가 0인 경우도 크게 다르지 않으니, 일단은 무시하고 진행하자)

이제, $10^5-1$을 곱해 보자. 그러면,

$100000-abcd = 9efgh$ 일 것이므로, $abc(d-1)9efgh$가 성립할 것이다.

 

즉, $abcd * 9999$ 와, $abcd * 99999$의 자릿수 합이 정확하 9만큼 차이가 나므로, 둘 중 하나는 반드시 홀수이다.

 

이것을 이용해서, $10^8-1$ 과 $10^9-1$ 을 곱해보고 둘 중 올바른 값을 찾으면 된다. 코딩은 쉬우니 이 방법은 생략.

---

별해

이 문제는 이상한 별해가 있다(...)

잘 생각해 보면, 전체 수 중에 대략 50% 쯤은 자릿수 합이 홀수여야 한다.

그러면 대충 숫자를 막 뽑아서 곱한다음 홀수인지 확인하고, 아니면 버려도 생각보다 빨리 찾아지지 않을까?

(더 엄밀하게는, 어떤 수에 대해서도 자릿수의 합이 홀수인 배수가 너무 드물지 않음을 보여야 하긴 하지만.)

 

매우 근본없는 코드인데, 3만번 뽑아보고 그안에 찾아지기를 기도한다. 

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

int checker(ll n)
{
    int sum = 0;
    while ( n > 0 )
    {
        sum += n % 10;
        n /= 10;
    }
    return sum%2;
}

int main()
{
    srand((unsigned int)time(0));
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        for (int i = 0; i<30000; i++)
        {
            ll k = rand()%(1000000000LL);
            if (checker(n*k))
            {
                printf("%lld\n",n*k);
                break;
            }
        }
    }
}

이게 왜 맞는지는 나중에 기회가 된다면? 알아보겠지만...

대충 몇개 잡아서 돌려보면 알겠지만 생각보다 규칙성이 별로 없다.

즉, 대충 홀짝성이 잘 균등(까지는 아니지만) 비슷하게 분포할 것이라고 믿자(...)