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 zhb_msqx at 2007-09-11 19:20:06 on Problem 2649
#include <iostream>
#include <fstream>
using namespace std;

int n,m;

int gcd(int a,int b){
	int max=a>b?a:b;
	int min=a<b?a:b;

	int r=1;
	while(r>0){
		r=max%min;
		max=min;
		min=r;
	}
	return max;
}

int func(){
	int i,j,k;
	j=m;

	for(i=n;i>=1;i--){
		int cdiv;
		cdiv=gcd(i,j);
		j=j/cdiv;
		if(j==1)return 1;
	}
	return j;
}


void main(){
//	cout<<gcd(100,15);
//	ifstream cin("data.txt");
	while(cin>>n>>m){
		if(n==0){
			if(m==1)cout<<"1 divides 0!"<<endl;
			else cout<<m<<" does not divide 0!"<<endl;
			continue;
		}
		if(m==0){
			cout<<0<<" does not divide "<<n<<"!"<<endl;
			continue;

		}

		if(func()==1){

			cout<<m<<" divides "<<n<<"!"<<endl;
		}else{

			cout<<m<<" does not divide "<<n<<"!"<<endl;
		}

	}
}

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