글 읽기 - TL뜹니다 이문제에서 벗어나고 싶습니다.

scared22 9년 전 0

분자 분모가 2와 5를 찾아서 카운트를 증가시키는데 좀 더 빠르게 탐색하는 방법이 없을까요 ?

#include <iostream>
#include <stdlib.h>
using namespace std;

int main()
{
	int n,m,temp,temp1,temp2;
	int twocount=0,twocount1=0,fivecount=0,fivecount1=0;
	int mi,mi1;
	

	cin>>n>>m;
	temp=n-m;

	for(int i=n;i>temp;i--)  //분자
	{
		temp1=i;
		while(temp1%2==0 || temp1%5 == 0)
		{
			if(temp1%2==0)
			{
				temp1/=2;
				twocount++;
			}
			else if(temp1%5==0)
			{
				temp1/=5;
				fivecount++;
			}
			else break;
		}
	}
	for(int j=m;j>1;j--) //분모
	{
		temp2=j;
		while(temp2%2==0 || temp2%5 == 0)
		{
			if(temp2%2==0)
			{
				temp2/=2;
				twocount1++;
			}
			else if(temp2%5==0)
			{
				temp2/=5;
				fivecount1++;
			}
			else break;
		}
	}
	/*cout<<twocount<<" "<<twocount1<<" "<<fivecount<<" "<<fivecount1<<endl;*/
	if(twocount == 0 || fivecount ==0)cout<<0<<endl;
	else if((twocount == twocount1) || (fivecount == fivecount1)) cout<<0<<endl;
	else if((twocount1==0) || (fivecount1==0))
	{
		if(twocount1 == 0)
		{
			mi=twocount;
			if(fivecount>fivecount1)
				mi1=fivecount-fivecount1;
			else
			{
				cout<<0<<endl;
				exit(1);
			}
		}
		if(fivecount1 == 0)
		{
			mi1= fivecount;
			if(twocount>twocount1)
				mi=twocount-twocount1;
			else
			{
				cout<<0<<endl;
				exit(1);
			}
		}
		if(mi>mi1)
			cout<<mi1<<endl;
		else
			cout<<mi<<endl;
	}
	else
	{
		mi=twocount-twocount1;
		mi1=fivecount-fivecount1;
		if(mi>mi1)
			cout<<mi1<<endl;
		else
			cout<<mi<<endl;
	}

}

	

	

kyma123 9년 전 1

일일히 세는 것 보단 2와 5 각각의 거듭제곱으로 나눈 몫을 이용하는 게 훨씬 빠르겠죠.

그리고 1억이 넘는 케이스를 완전탐색 하면 대부분 TL 뜬다 생각하시는 게 좋습니다.

scared22 9년 전 0

이렇게 해도 TL이네요

	for(int i=2;i<=n;i*=2)
	{
		for(int j=temp+1;j<=n;j++)//분자
		{
			if(j%i==0)
				twocount++;
		}
		for(int j=m;j>1;j--) //분모
		{
			if(j%i==0)
				twocount1++;
		}
	}
	for(int i=5;i<=n;i*=5)
	{
		for(int j=temp+1;j<=n;j++)//분자
		{
			if(j%i==0)
				fivecount++;
		}
		for(int j=m;j>1;j--)//분모
		{
			if(j%i==0)
				fivecount1++;
		}
	}

kesakiyo 9년 전 3

http://www.geeksforgeeks.org/count-trailing-zeroes...

이 링크가 도움을 줄거라 생각합니다.

직접적인 솔루션은 들어있지 않지만 빠르게 2와 5의 개수를 셀 수 있게 해줄거에요.

kyma123 9년 전 2

음 그렇게 count에 ++하는 것 보단, n!의 뒷자리 0의 갯수 문제 풀듯이 푸는 쪽이 좋겠습니다.

우선 nCk = n! / k!(n-k)!이므로, n에 포함된 2와 5의 갯수를 다음과 같이 셉니다.

N₂ = Σ[n/2^k], k=1, 2, ..., N₅ = Σ[n/5^k], k=1, 2, ...

같은 방식으로 k와 n-k도 세 준 다음 그것을 뺀 후, N₂와 N₅ 중 작은 값을 출력하면 되겠죠.

이 때 2^k 혹은 5^k가 32비트 정수라면 오버플로우가 일어날 가능성이 있으므로 처리를 따로 하시던지 64비트 정수로 선언하시던지 해야겠죠

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

TL뜹니다 이문제에서 벗어나고 싶습니다.

scared22 9년 전 0

kyma123 9년 전 1

scared22 9년 전 0

kesakiyo 9년 전 3

kyma123 9년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말