Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

我的程序为啥超时了啊???

Posted by AutoGerk at 2009-07-16 13:26:08 on Problem 2891
#include <cstdio>

__int64 gcd(__int64 m,__int64 n)
{
	__int64 r;
	while(n)
	{
		r=m%n;
		m=n;
		n=r;
	}
	return m;
}

int main()
{
	__int64 N,k,i,re,tn,tre,mc;
	bool found=true;
	while(scanf("%I64d",&k)!=EOF)
	{
		scanf("%I64d%I64d",&N,&re);
		for(i=1;i<k;++i)
		{
			scanf("%I64d%I64d",&tn,&tre);
			mc=N*tn/gcd(N,tn);
			while((re-tre)%tn)
			{
				re+=N;
				if(re>tre+mc)
				{
					found=false;
					break;
				}
			}
			if(!found)
				break;
			N=mc;
		}
		if(!found)
			printf("-1\n");
		else
			printf("%I64d\n",re);
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator