[백준 2004번 c#] 조합 0의 개수

728x90

- 조합:  n!/(n-r)!r! 

1. n!의 2,5 개수 , (n-r)! 의 2,5의 개수, (r!)의 2,5의 개수 구하기
2. n!의 2의 수에서 (n-r)! 와 r! 2의 수 더한거를 빼준다
3.  n!의 5의 수에서 (n-r)! 와 r! 5의 수 더한거를 빼준다
4. 2,3번 중에 더 작은 값이 정답

 

 

using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Project2
{
    class Class1
    {
        static void Main(string[] args)
        {
            StreamWriter writer = new StreamWriter(Console.OpenStandardOutput());
            StreamReader reader = new StreamReader(Console.OpenStandardInput());
            StringBuilder sb = new StringBuilder();

            //[1]입력
            string[] str = reader.ReadLine().Split();
            long N = long.Parse(str[0]);
            long M = long.Parse(str[1]);


            long fiveCount= fivePower(N) - fivePower(N-M)-fivePower(M);
            long twoCount = twoPower(N) - twoPower(N - M) - twoPower(M);

            writer.WriteLine(Math.Min(fiveCount, twoCount));    

            writer.Close();
            reader.Close();

        }

        //5의 승수 구하기
        static long fivePower(long num)
        {
            long count = 0;
            while (num >= 5)
            {
                count += num / 5;
                num /= 5;
            }
            return count;
        }

        //2의 승수 구하기
        static long twoPower(long num)
        {
            long count = 0;
            while (num >= 2)
            {
                count += num / 2;
                num /= 2;
            }
            return count;
        }
    }

}