這題最簡單的方法居然是暴力。。。
時間復雜度一算大概是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;
}