SNUPS PS-INTRO 4주차 풀이 (2)
알고리즘 문제풀이/SNUPS PS Intro 2019 2019. 5. 20. 03:32풀이 포스팅 (1) 에서 풀지 않은 아래 6문제 중 3문제를 먼저 풀자. 가능하면 월요일 중으로 (3) 도 쓰고 싶은데..흠..
1676. 팩토리얼 0의 개수
이제부터 슬슬 IDE보다는 노트와 펜을 꺼내들어야 하는 문제들을 준비하려고 노력했다. 특히 프로그래밍은 해봤지만, PS 문제풀이 경험이 없는 사람을 대상으로 하는 스터디 특성상 그런 것들이 더 많이 필요하다고 생각하기도 하고..
먼저, 끝에 0이 왜 많이 나오는지를 생각해 보자. 당연히, 10의 제곱이 많이 들어가기 때문이다.
10의 제곱은 왜 많이 들어갈까? 2랑 5의 제곱이 많이 들어가기 때문이다.
구체적으로, 다음을 간단히 보일 수 있다. 만약 어떤 수 $N$ 을 소인수분해 했을 때,
$$ N = 2^m 5^n k$$ 형태이고, k에는 2와 5가 들어 있지 않다면, $N$의 끝자리에는 $\min(m,n)$개의 0이 오게 된다.
즉, $n!$을 소인수분해했을 때 2와 5의 지수가 몇개인지를 세면 된다.
조금만 생각해보면, 언제나 둘 중에는 2의 지수가 더 크거나 같을 것이라는 것을 쉽게 생각할 수 있다. 2의 배수가 5의 배수보다 훨씬 많기 때문에. 따라서, 둘 중에는 다시 5의 지수만 세 보면 된다.
$n!$ 에서 5의 지수를 세는 것은 쉽지 않은 일이다. 예를 들어, $4!$ 에는 5가 한 번도 들어가지 않지만, $5!$ 에는 한 번, $10!$ 에는 두 번, $25!$ 에는 여섯 번 들어간다. 즉, $k$를 곱할 때마다, $k$가 5로 나누어 떨어지는 횟수를 계속 더해 주면 된다. (25의 경우, 5에서 한 번, 10에서 한 번, ... 25에서 두 번)
이 생각을 코드로 구현하면 아래와 같다.
#include <bits/stdc++.h>
using namespace std;
int power_of_five(int k)
{
int i = 0;
while (true)
{
if (k % 5 == 0)
{
k = k / 5;
i++;
}
else
break;
}
return i;
}
int main()
{
int n;
int c = 0;
int i;
scanf("%d", &n);
for (i = 1; i <= n; i++)
c += power_of_five(i);
printf("%d", c);
}
이 문제는 제한이 크지 않아서 이런 풀이에도 아무런 문제가 없다. 그렇지만 조금만 더 쉽게 구하는 방법을 생각해 보자.
만약에 30!에서 5의 지수를 구한다면, 이렇게 생각해 볼 수 있다.
1번 나누어 떨어지는 수 : 6개 (5, 10, 15, 20, 25, 30)
2번 나누어 떨어지는 수 : 1개 (25)
여기서, 주목할 점은
1번 나누어 떨어지는 수는 $\left[ \frac{n}{5} \right]$ 개 있고
2번 나누어 떨어지는 수는 $\left[ \frac{n}{5^2} \right]$ 개 있다.
따라서, 다음 식이 그대로 답이 된다.
(그 가우스 기호이다)
무한대까지 더한다고 해서 약간 당황스러울 수 있지만, 수학적으로 저렇게 쓴 것일 뿐, 생각해보면 i가 일정 이상 커지면 모두 0이 될 것이라서 그 이후는 그만 더해도 된다.
2981. 검문
숫자 $N$개가 주어지고, 이 숫자들을 $M$ 으로 나누었을 때 나머지가 모두 같게 되는 $M$을 모두 찾으려고 한다.
먼저, 이 문제를 수식으로 써 보자.
$$a_1 = q_1 M + r $$
$$a_2 = q_2 M + r $$
$$a_3 = q_3 M + r $$
...
이런 식들이 모두 성립한다고 한다.
이제, 우리가 이 식을 직접 다루기 어려운 이유가 무엇인지 파악해 보자. 나머지 $r$ 이 없다면, 모든 항들의 gcd를 취하여 $M$ 의 값을 구할 수 있을 것이다.
또한, 어떤 $X$ 가 저 식을 만족한다고 주어진다면, $X$의 임의의 약수 $t$ 도 저 식을 만족한다. 왜인지는 쉬운데, $qM$ 부분은 여전히 $t$의 배수일 것이고, 뒤의 $r$은 모두 같으므로 $t$로 나눈 나머지들도 다시 같을 것이기 때문이다.
따라서 우리는 최대의 $M$ 하나만 구하면 되며, 그런 $M$의 약수들이 우리가 원하는 값이라는 것을 알 수 있다.
이제, gcd를 이용하여 저 값을 구하기 위해, 저 숫자들을 정렬한 다음 (음수가 생기면 귀찮으니까...)
$a_2 - a_1$, $a_3 - a_2$, $a_4 - a_3$ 같은 값들을 생각하자. 이들은 모두 $(q_2 - q_1) M$, $(q_3 - q_2) M$ 같은 형태일 것이므로, 여전히 $M$의 배수이다. 우리가 원하는 것은 최대한 큰 $M$을 원하므로, 이 모든 값들의 gcd를 취하자.
그렇게 얻어진 $M_{max}$ 의 약수를 모두 출력해주면 된다. 1은 출력하지 않음에 유의하자. 그리고 약수를 출력할 때, 한번에 i랑 n/i를 저장하는 것은 좋지만 출력은 크기 순으로 해야 하므로 그대로 출력해서는 안 되며, 예를 들어 16의 약수를 저장할 때 4가 두번 들어가지 않도록 조심해야 한다.
#include <bits/stdc++.h>
#define lli long long int
#define bignum (int)1e9
using namespace std;
int gcd(int a, int b)
{
return b ? gcd(b, a%b) : a;
}
vector <int> v;
int numbers[102];
int adjgap[102];
int main()
{
int g;
int n;
scanf("%d",&n);
for (int i = 0; i<n; i++)
{
int x;
scanf("%d",&x);
numbers[i] = x;
}
sort(numbers,numbers+n);
for (int i = 1; i<n; i++)
adjgap[i] = (numbers[i]-numbers[i-1]);
g = adjgap[1];
for (int i = 1; i<n; i++)
g = gcd(adjgap[i],g);
int t = (int)sqrt(g)+1;
v.push_back(g);
for (int i = 2; i<t; i++)
{
if (g%i==0 && i != g/i)
{
v.push_back(i);
v.push_back(g/i);
}
if (g%i == 0 && i == g/i)
v.push_back(i);
}
sort(v.begin(),v.end());
int size = v.size();
for (int i = 0; i<size; i++)
printf("%d ",v[i]);
}1016. 제곱 ㄴㄴ 수
놀라운 정답률 (18.743%) 을 보여주는 문제.
사실은 지금은 학기중이라 바쁠 것이기 때문에, 스터디원들이 이 문제까지 혼자서 열심히 고민해서 풀어본다면 정말 좋겠지만 끝 4문제 (제곱 ㄴㄴ 수, GCD(n, k) = 1, 오민식, 안수빈수) 는 조금 많이 어렵게 느껴질 것이라는 생각도 든다. 그러나 각각의 문제에서 꼭 얘기하고 싶은 것들이 하나씩 있어서 넣었다...
1부터 $10^{12}$ 까지의 구간에서, 최대 100만의 길이를 갖는 구간 (a,b)를 뽑았을 때, 몇 개의 square-free 한 자연수 (제곱수로 나누어 떨어지지 않는 자연수를 square-free라고 한다) 가 있는지를 세는 문제이다.
어떤 자연수가 제곱수로 나누어 떨어진다고 해 보자. 즉, $N = m^2 k$를 만족하는 자연수 $m \neq 1$ 이 존재한다.
우리는 각각의 $m$을 보면서 이 문제를 풀 수 있다.
최댓값과 최솟값은 매우 크거나 작을 수 있지만, 중요한 것은 그 간격은 100만으로 제한되어 있다는 점이다. 그리고 어차피 $m$을 제곱해야 해서, $m$은 $\sqrt{b}$ 이하임은 자명하다. 따라서, 2부터 $\sqrt{b}$까지 돌면서, 100만개짜리 배열 arr를 다음과 같이 갱신하자.
"만약 $m^2$가 $i+a$ 을 나누면, arr(i) 를 1로 바꾼다"
이렇게 모두 돌아줄 것인데, 모든 제곱수를 다 쓰면 당연히 안 되고, a보다 작은 값들은 그냥 스킵해준다.
이 생각을 코드로 작성하면 아래와 같다.
이번 구현에서 주의할 점은, arr(i) 가 i에 대한 정보를 담은 게 아니라, i+a의 정보를 담았다는 것이다. minimum이 10억이면, arr(10)은 10이 square free 인지가 아니라 10억 10이 square free 인지를 담은 것이다.
#include <bits/stdc++.h>
#define lli long long int
using namespace std;
int check[1020000];
int main()
{
lli mini,maxi;
scanf("%lld%lld",&mini,&maxi);
int c=0;
for (lli i = 2; i*i<=maxi; i++)
{
lli u = i*i*(mini/(i*i));
while(u<=maxi)
{
if (u>=mini)
check[u-mini]=1;
u += (i*i);
}
}
for (lli j = mini; j<=maxi; j++)
c += (1-check[j-mini]);
printf("%d",c);
}여담
어떤 자연수가 제곱수로 나누어 떨어진다고 해 보자. 즉, $N = m^2 k$를 만족하는 자연수 $m \neq 1$ 이 존재한다. 이때, $m$은 당연히 소인수분해가 가능할 것이므로, 어떤 소수 $p$가 존재하여 $N = p^2 X$이다.
따라서, 모든 수를 파악할 필요가 없고... 소수의 제곱으로 나누어 떨어지는지 여부만 세면 된다.
진짜 여담
(스킵해도 된다)
전혀 안 그래 보이지만, square-free인지의 여부는 정수론에서 굉장히 중요한 주제이다.
심지어는, 다음과 같이 정의된 함수가 있다.
$n$이 square free이면
$n$의 소인수가 짝수개이면 1
$n$의 소인수가 홀수개이면 -1
$n$이 square free가 아니면 0.
이 함수를 $\mu(n)$ 이라고 쓰고, Möbius function (뫼비우스 함수) 라고 부른다. "뫼비우스 띠" 의 그 뫼비우스 맞다.
진짜 진짜 여담
(갑자기 생각나서 적은거니까 스킵하는게 이 포스팅의 본 목적에 맞는다)
위에서 언급한 뫼비우스 함수는 정말 신기한 특성들을 많이 갖는다.
예를 들어...
$$ \sum_{n = 1}^{\infty} \frac{\mu(n)}{n^s} = \frac{1}{\zeta(s)}$$
우변의 분모에 들어간 이상한 그리스 문자는 제타이다. 저 "제타함수" 는, 다른 이름으로 리만 제타 함수라고 부르는데,
리만 가설 : 리만 제타 함수의 모든 비자명해의 실수부는 $\frac{1}{2}$이다.
이 리만 제타 함수이다.
그리고,
$$ M(x) = \sum_{n = 1}^{x} \mu(x) $$ 이렇게 정의된 $M$함수에 대해서, 모든 $\epsilon>0$에 대해 (즉, 아무리 작은 $\epsilon$이더라도 양수이기만 하면)
$$ |M(x)| = \mathcal{O}(x^{\frac{1}{2}+\epsilon})$$ 일 것이라는 추측이 있다. 즉, 아무리 작은 입실론을 잡아도 결국에는 $|M(x)|$ 보다 커지게 될 것이라는 건데...
이 추측은 리만 가설과 동치인 명제이다. (참고로, $\epsilon = 0$ 일 때, 즉 $|M(x)| = \mathcal{O}(\sqrt{x})$ 는 Mertens conjecture라고 해서, 지금 말한 명제보다 아주 약간 더 강한데 (즉, 리만 가설보다 약간 더 강하다!) 1985년에 거짓인 것으로 증명되었다. 1990년대 초에는, $|M(x)|$ 의 order가 대략 $\mathcal{O}(\sqrt{x} (\log\log\log x)^{5/4})$ 일 것이라는 추측이 제기되었으며 증명되지 않았다.)
'알고리즘 문제풀이 > SNUPS PS Intro 2019' 카테고리의 다른 글
| SNUPS PS-INTRO 4주차 풀이 (3) (0) | 2019.05.21 |
|---|---|
| SNUPS PS-INTRO 4주차 풀이 (1) (0) | 2019.05.19 |
