[일반] 실버문제 질문점

[익명(119.195)]

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

Baekjoon Online Judge

이 문제 어떻게 푸는거야 해설 가능한 행님들 있나..

[노는게제일좋아(aig0016)]

모듈러 연산을 아십니까

[익명(119.195)]

% 이거 말씀하시는거 아닌가요?? 분배법칙 가능하다 까지만 알고 있음

[노는게제일좋아(aig0016)]

첫째자리까지만 알면 되니까 팩토리얼 구하면서 0 생길때마다 나누기로 날리고 곱해지는 수보다 커지지 않게 모듈러로 앞자리 수 쳐내셈

[익명(103.114)]

모듈러를 큰 걸로 쓰면 문제 N 범위에서 정답처리 될 수는 있지만 이론적으로는 틀린 방법임. 예를 들어 %10000 씌우면 3125에서 오답 나옴.

[노는게제일좋아(aig0016)]

long long 안에서 적당히 큰값 잡으면 N=10000은 충분하지 않나

[익명(103.114)]

간단하게 말하면 0의 개수가 N!을 5로 몇 번 나눌 수 있는지 횟수랑 같다는 걸 이용해서 (1...N 수 각각을 2랑 5로 나눌 수 있는 한 최대한 나눈 다음 1의 자리끼리 곱) * (2^(N!을 2로 나눌 수 있는 횟수 - N!을 5로 나눌 수 있는 횟수))의 1의 자리를 구하면 됨. N 범위가 작으니까 전부 전처리한 다음 배열에 때려박는 치사한 방법도 있음.

[익명(218.233)]

2,5로 나누어지는 수 곱해질때마다 카운팅 해둔다음 1의 자리수만 mod10해서 구해두고 넘치는 2,5중 더 카운트 많이 된 수를 그만큼 곱해주기 예를 들어 2가 5번 5가 4번이면 2로 한번 곱한걸로 생각하면 될거같은데