这题最简单的方法居然是暴力。。。
时间复杂度一算大概是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;
}