The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

关于浙大月赛I题的一些思考 还是TLE,求解

这题最简单的方法居然是暴力。。。
时间复杂度一算大概是N^2,AC了。。。
#include<iostream>
#include
<cstdio>
#include
<cstring>
using namespace std;
//暴力求因子,打表 
int n;
int a[1000001],b[1000001]={0},c[1000001]={0},d[1000001]={0};
void init()
{
    
int i,j,k;
    
for(i=1;i<=1000000;i++)
    
for(j=1;j*i<=1000000;j++)b[i*j]++;                      
    
for(i=1;i<=1000000;i++)
    
{
        a[i]
=d[b[i]];                   
        d[b[i]]
++;                   
        }
           
    }

int main()
{
    init();
    
while(scanf("%d",&n)!=EOF)
    
{
          printf(
"%d\n",a[n]);                    
          }

    
return 0;
    }
 

我来说说我对这个题的想法
一。首先我们需要将每个元素对应的约数个数算出来。
可以分解质因数,然后用数学公式计算。
由于最大数是10^6,所以我们只需打出10^3以内的素数表,根据素数筛选法复杂度,我们可以确定大概是n左右,1000,几乎可以忽略不计。
二。打出素数表来以后可以用素数表里面的数对原来的数进行分解质因数,然后即可算出所有数对应的约数个数。
三。将输入全部读入后,排序,nlogn,n最大为1000,时间也基本可忽略吧。
四。从1-100000进行线性扫描,求出题目所要求的f[n],复杂度是n,n最大是10^6;
最后复杂度应该是线性的,但为什么超时..请各位大牛指点。。。

#include<iostream>
#include
<cmath>
#include
<cstring>
#include
<cstdio>
using namespace std;


int a[1000001]={0};//存n有多少个约数
int b[1010]={0};//存约数是n个数有多少个

struct node
{
    
int id;
    
int num;
}
c[1000001];
int cmp(const void *a,const void *b)
{
    
return ((node*)a)->num -((node*)b)->num;
}


int ans[10001];







#define MAX 1001
int prime[MAX+1]={0};
bool isprime[MAX+1]={0};
int len=0;
void get_prime()//这是一个基于素数筛选的线性算法,很快
{
    
int i,j;
    
    
for(i=2;i<=MAX;i++)
    
{
        
if(isprime[i]==false//false代表是质数
        {
            prime[
++len]=i;
        }

        
for(j=1;j<=len&&prime[j]*i<=MAX;j++)
        
{
            isprime[prime[j]
*i]=true;//true代表是合数
            if(i%prime[j]==0)
            
{
                
break;
            }

        }

    }

}





int main()
{
    
int n;
    
int i=1;
    
int innum=0;
    
int k;
    
int p=1;
    get_prime();
    
while(scanf("%d",&c[i].num)!=EOF)
    
{
        c[i].id
=i;
        i
++;
    }

    innum
=i-1;
    qsort(c
+1,innum,sizeof(c[1]),cmp);

    
for(n=1;n<=1000000;n++)
    
{
        k
=n;
        
int res=1;
        
int cnt=0;
        
for(i=1;i<=len;i++)
        
{
            
            cnt
=0;
            
while(k%prime[i]==0&&k!=1)
            
{
                
                k
/=prime[i];
                cnt
++;
            }

            
if(cnt!=0)
            
{
                res
*=(cnt+1);
            }

            
if(prime[i]>sqrt((double)k+1) )
                
break;
            
            
if(k==1)
                
break;
        }

        
if(k!=1)
            res
*=2;
        a[n]
=res;
        b[res]
++;
        
while(n==c[p].num)
        
{
            ans[c[p].id]
=b[a[i]]-1;
            p
++;
        }

    



    }


    
for(i=1;i<=innum;i++)
    
{
        printf(
"%d\n",ans[i]);
    }


    
    
return 0;
}


posted on 2009-12-15 01:01 abilitytao 阅读(1398) 评论(1)  编辑 收藏 引用

评论

# re: 关于浙大月赛I题的一些思考 还是TLE,求解 2009-12-27 23:45 MasterLuo

这题最简单的方法是类似于线性筛选法的打表。
S=x^a1*y^a2*...*z^a3的结果为(a1+1)*(a2+1)*(a3+1)...  回复  更多评论   


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理