4개의 댓글이 있습니다.
-
-
hyunhwan -
http://acm.pku.edu.cn/JudgeOnline/problem?id=1401 엮임문제로 하나 추가 'ㅅ' 덕분에 한문제 풀었어용 감사감사
17년 전 link
-
-
-
JongMan -
어떤 숫자 k 를 2로 n번 나눌 수 있다고 합시다. 그러면 k 는 2^n 의 배수겠죠.
ai 중에 2의 배수가 몇 개나 있을까요? ai/2 개 있겠죠.
ai 중에 2^2의 배수는 ai/(2^2) 개 있을 테고..
2^3 의 배수는 ai/(2^3) 개 있을 테죠.
이들의 수를 다 더하면, 2^3 의 배수들은 2^2 의 배수 셀때도 카운트 되고 2^1 의 배수 셀 때도 카운트 되니 3번 카운트 되고..
모든 2^n 의 배수들 (최대 2^n 이라는 얘깁니다.. 2^(n+1) 의 배수가 아닌) 은 n번씩 카운트 되겠죠. ^^
17년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
astein
F - Factorial [문제링크]
n! 을 b 진수로 표현했을 때 뒤에 0이 몇 개나 붙는지를 세는 문제입니다.
만약, b가 소수(prime number)라면 n! 에 b 가 몇 번이나 곱해져 있는지만 counting 하면 됩니다. :-D 하지만 b가 합성수(composite number)인 경우, b를 인수분해 하여 각각의 인수들이 몇 번씩 곱해져 있는지를 counting 해 줘야 합니다.
b = a1^p1 * a2^p2 * ... * ak^pk (a1, a2, ..., ak = prime number, p1, p2, .., pk > 0) 이라고 합시다.
n!에 어떤 소수 ai 가 몇 번 곱해져 있는지를 counting하는 알고리즘은 아래와 같습니다.
[spoiler="더 보기..."] ai의 계수 = n / ai + n / ai^2 + n / ai^3 + ...
[/spoiler]
만약에 b를 인수분해 했을때 2가 3번 곱해져 있고 n!에 2가 97번 곱해져 있다고 가정하면, 이 경우 n!에 0이 최대한 많이 들어간다고 하면 97 / 3 = 32.xxx = 32번까지 사용 가능합니다. 모든 소수에 대하여 위의 과정을 반복하면 0이 몇 개나 나오는지 셀 수 있습니다.
--- (설명이 부족한 듯 싶은데, 댓글로 달아주시면 추가해 드리겠습니다.) ---
17년 전