심심한 사람 내가 6시간 삽질한 문제 풀어봐라

[란순이자2지(pls213)]

문제

nCm의 끝자리 0의 개수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 n, m(0≤m≤n≤2,000,000,000, n!=0)이 들어온다.

출력

첫째 줄에 0의 개수를 출력한다.

예제 입력

25 12

예제 출력

2

[^_^(175.223)]

얼ㅋ 이따 풀어볼게요 ㅋㅋ ㅋ_ㅋ

[ㅁㄴㅇㅁㄴㅇ(125.138)]

몇살이냐

[익명(121.144)]

6분이면 풀겠네요

[asd(98.212)]

좆나 쉬운데

[＋백왕＋(whiteprince)]

어휴 프갤수준;;;;;

[아놔콘다(anwaconda)]

1)임의의 수 n이 0으로 끝나려면 소인수분해 했을때 반드시 2와 5 를 소인수로 가져야한다. 예를 들어서 소인수 집합에서 2가 3개, 5가 2개이면 두개의 0으로 끝나는 수이다(2*5*2*5). 즉 m개의 숫자가 주어졌을때 각 숫자에서 2*5 집합의 개수를 누적 카운팅하면 되는데....

[olduck(112.146)]

문제가 이해가안됨

[＋백왕＋(whiteprince)]

우와 아놔콘다 똑똑하다

[＋백왕＋(whiteprince)]

글쓴이는 long long 보다 큰 데이터형 만들어서 했을듯 ^0^

[아놔콘다(anwaconda)]

2) 문제에서 제시하는 숫자의 범위가 상당히 크기 때문에 n! / ( (n-k)!*k! ) 을 무식하게 계산하면 안됨.

[^_^(175.223)]

팩토리얼 안 써도 되니까 int만으로 해결 가능하지않아요?_?

[아놔콘다(anwaconda)]

3) 우선은 팩토리얼 나누기를 압축해주는 알고리즘을 고안해야 함. 12! / (3!*9!) 을 12*11*10/3!로 줄이는 식으로.... 그리고 분모와 분자를 나누면서 2 또는 5로 나누어지지 않는 숫자는 과감히 버림(어차피 곱해도 0으로 끝나지 않는 숫자들임)

[아놔콘다(anwaconda)]

4) 이 문제는 얼핏 보면 팩토리얼 계산하는 것 같지만 2와 5의 소인수 갯수를 구하는 문제... 추가로 메모리가 충분히 허용된다면 메모이제이션으로 속도 향상을 누릴 수 있음 ( n! 에서 2의개수가 x, 5의 개수가 y개이면 (n+1)!은 n+1의 2, 5개수를 구해서 누적해주는 식)