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

why TLE!!!!!

Posted by PK_ILGYU at 2006-03-28 19:08:17 on Problem 2773
#include<stdio.h>
#define Max_n 1000000

int N,K;
//__int64 Dap,L,Count;
int Dap,L,Count;

int P[1000000],Pcnt;

int A[100],Cnt;

void prime()
{
	int i,j,sw;

	for(i=2; i<=Max_n; i++){
		sw=0;
		for(j=2; j*j<=i; j++){
			if(i%j==0){
				sw=1;
				break;
			}
		}
		if(sw==0){
			P[Pcnt]=i;
			Pcnt++;
		}
	}
}

void insubunhae()
{
	int n,i=0,sw=0;

	n=N;

	for(;;){
		if(i==Pcnt || n==1) break;
		if(n%P[i]==0){
			n/=P[i];
			if(sw==0){
				A[Cnt]=P[i];
				Cnt++;
			}
			sw=1;
		}else{
			sw=0;
			i++;
		}
	}
}

void recall(int cnt, int gop, int use)
{
	if(cnt==Cnt){
		if(gop==1) return;
		if(use%2){
			Count+=(L-1)/gop;
		}else{
			Count-=(L-1)/gop;
		}
		return;
	}
	if(gop*A[cnt]<L){
		recall(cnt+1,gop*A[cnt],use+1);
	}
	recall(cnt+1,gop,use);
}

void process()
{
	int st,ed,mid;
	int i,sw;

	st=1; ed=2000000000;
	for(;;){
		mid=(st+ed)/2;

		L=mid; Count=0;
		recall(0,1,0);

		if(L-Count<K){
			st=mid+1;
		}else if(L-Count>K){
			ed=mid-1;
		}else{
			sw=0;
			for(i=0; i<Cnt; i++){
				if(L%A[i]==0){
					sw=1;
					break;
				}
			}
			if(sw==0){
				Dap=L;
				break;
			}else{
				st=mid+1;
			}
		}
	}
}

int main()
{
	FILE *fin=fopen("2773.in","r");
	FILE *fout=fopen("2773.out","w");

	prime();
	
	for(;;){
		N=0;
		fscanf(fin,"%d%d",&N,&K);
//		scanf("%d%d",&N,&K);
		if(N==0) break;
		insubunhae();
		process();

		fprintf(fout,"%d\n",Dap);
//		printf("%d\n",Dap);
		Cnt=0;
	}
	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