Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

TLE的程序

Posted by mixter at 2006-09-16 18:33:46 on Problem 2992
In Reply To:为何这个程序过了？但是下面那个TLE？不理解，希望有牛给个解释 Posted by:mixter at 2006-09-16 18:32:23

#include <iostream>
using namespace std;
#define MAX 300
#define MAXP (2*MAX+1)
__int64 n,k;
int primes[MAXP],isprime[MAXP];
__int64 ans[500][500];
__int64  factpow(int n,int p)
{   
	if(ans[n][p]!=-1) return ans[n][p];
	__int64 d=0;
	do
	{
		n /= p;
		d += n;
	}while(n);
    ans[n][p]=d;
	return d;
}
__int64 ndivs(int n,int k)
{
	__int64 i,ad;
	__int64  nd=1;

	for(i = 0; primes[i] <= n; i++)
	{
		ad = factpow(n,primes[i]) - factpow(k, primes[i]) - factpow(n-k,primes[i]);
		nd *= (ad + 1);
	}
	return nd;
}
int main()
{
	//freopen("test.txt","r",stdin);
	int n,k,i,j;
	isprime[1]=1;
	n = 0;
	for(i = 2;i < MAXP; i++)
		if(!isprime[i])
		{
			primes[n++] = i;
			for(j = 2 * i; j < MAXP; j += i)
				isprime[j] = 1;
		}
//	memset(ans,0,sizeof(ans));
	for(n=0;n<=450;n++)
	{
		for(k=0;k<=450;k++)
			ans[n][k]=-1;
	}
	while(scanf("%d%d",&n,&k)==2)
	{			
		printf("%I64d\n",ndivs(n,k));
	}
	return 0;
}

Followed by:

第二个超时是因为你犯了一个很马虎的错误 (238) ACM06021fly 2006-09-17 01:14:03
- 哦~~我是猪 (4) mixter 2006-09-17 11:53:55

Post your reply here:

User ID:
Password:
Title:

Content:

> #include <iostream>
> using namespace std;
> #define MAX 300
> #define MAXP (2*MAX+1)
> __int64 n,k;
> int primes[MAXP],isprime[MAXP];
> __int64 ans[500][500];
> __int64  factpow(int n,int p)
> {   
> 	if(ans[n][p]!=-1) return ans[n][p];
> 	__int64 d=0;
> 	do
> 	{
> 		n /= p;
> 		d += n;
> 	}while(n);
>     ans[n][p]=d;
> 	return d;
> }
> __int64 ndivs(int n,int k)
> {
> 	__int64 i,ad;
> 	__int64  nd=1;
> 
> 	for(i = 0; primes[i] <= n; i++)
> 	{
> 		ad = factpow(n,primes[i]) - factpow(k, primes[i]) - factpow(n-k,primes[i]);
> 		nd *= (ad + 1);
> 	}
> 	return nd;
> }
> int main()
> {
> 	//freopen("test.txt","r",stdin);
> 	int n,k,i,j;
> 	isprime[1]=1;
> 	n = 0;
> 	for(i = 2;i < MAXP; i++)
> 		if(!isprime[i])
> 		{
> 			primes[n++] = i;
> 			for(j = 2 * i; j < MAXP; j += i)
> 				isprime[j] = 1;
> 		}
> //	memset(ans,0,sizeof(ans));
> 	for(n=0;n<=450;n++)
> 	{
> 		for(k=0;k<=450;k++)
> 			ans[n][k]=-1;
> 	}
> 	while(scanf("%d%d",&n,&k)==2)
> 	{			
> 		printf("%I64d\n",ndivs(n,k));
> 	}
> 	return 0;
> }

Home Page Go Back To top