這題最簡單的方法居然是暴力。。。
時間復雜度一算大概是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;
} 我來說說我對這個題的想法
一。首先我們需要將每個元素對應的約數(shù)個數(shù)算出來。
可以分解質(zhì)因數(shù)，然后用數(shù)學公式計算。
由于最大數(shù)是10^6，所以我們只需打出10^3以內(nèi)的素數(shù)表，根據(jù)素數(shù)篩選法復雜度，我們可以確定大概是n左右，1000，幾乎可以忽略不計。
二。打出素數(shù)表來以后可以用素數(shù)表里面的數(shù)對原來的數(shù)進行分解質(zhì)因數(shù)，然后即可算出所有數(shù)對應的約數(shù)個數(shù)。
三。將輸入全部讀入后，排序，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有多少個約數(shù)
int b[1010]={0};//存約數(shù)是n個數(shù)有多少個
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()//這是一個基于素數(shù)篩選的線性算法，很快
{
int i,j;
for(i=2;i<=MAX;i++)
{
if(isprime[i]==false) //false代表是質(zhì)數(shù)
{
prime[++len]=i;
}
for(j=1;j<=len&&prime[j]*i<=MAX;j++)
{
isprime[prime[j]*i]=true;//true代表是合數(shù)
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;
}