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:32:23 on Problem 2992

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

	for(i = 0; primes[i] <= n; i++)
	{
		ad =  set(n,primes[i]) - set(k, primes[i]) -  set(n-k,primes[i]);
		nd *= (ad + 1);
	}
	return nd;
}
int main()
{
	//freopen("test.txt","r",stdin);
	int n,k,i,j;
	isprime[1]=1;
for(i=0;i<432;i++){
for(j=0;j<432;j++){
dp[i][j]=-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;
		}
	while(scanf("%d%d",&n,&k)==2)
	{
		printf("%I64d\n",ndivs(n,k));
	}
	return 0;
}

Followed by:

TLE的程序 (960) mixter 2006-09-16 18:33:46
- 第二个超时是因为你犯了一个很马虎的错误 (238) ACM06021fly 2006-09-17 01:14:03
  - 哦~~我是猪 (4) mixter 2006-09-17 11:53:55
不小心贴代码了,ST帮忙删除下，谢谢！（前面的程序400多MS,后面超时） (1073) mixter 2006-09-16 18:34:41
- Ax太不厚道了 (0) frkstyc 2006-09-16 18:41:33
  - .....不管我事~~~~-_- (0) ArXoR 2006-09-16 18:43:26
    - 毛....就是你就是你就是你~~~~ST把前面的程序删掉吧~ (0) mixter 2006-09-16 18:44:02
      - 暂时没办法删…… (0) frkstyc 2006-09-16 18:44:26

Post your reply here:

User ID:
Password:
Title:

Content:

> #include <iostream>
> using namespace std;
> #define MAX 220
> #define MAXP (2*MAX+1)
> __int64 n,k;
> int primes[MAXP],isprime[MAXP];
> __int64 dp[440][440];
> int  factpow(int n,int p)
> {
> 	int d=0;
> 	do
> 	{
> 		n /= p;
> 		d += n;
> 	}while(n);
> 	return d;
> }
> __int64 set(__int64 n, __int64 k){
> if(dp[n][k]!=-1)
> return dp[n][k];
> dp[n][k]=factpow (n,k);
> return dp[n][k];
> }
> __int64 ndivs(int n,int k)
> {
> 	int i,ad;
> 	__int64  nd=1;
> 
> 	for(i = 0; primes[i] <= n; i++)
> 	{
> 		ad =  set(n,primes[i]) - set(k, primes[i]) -  set(n-k,primes[i]);
> 		nd *= (ad + 1);
> 	}
> 	return nd;
> }
> int main()
> {
> 	//freopen("test.txt","r",stdin);
> 	int n,k,i,j;
> 	isprime[1]=1;
> for(i=0;i<432;i++){
> for(j=0;j<432;j++){
> dp[i][j]=-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;
> 		}
> 	while(scanf("%d%d",&n,&k)==2)
> 	{
> 		printf("%I64d\n",ndivs(n,k));
> 	}
> 	return 0;
> }

Home Page Go Back To top