Let f(n) be the number of factors of integer n.
Your task is to count the number of i(1 <= i < n) that makes f(i) = f(n).
Input
One n per line (1 < n <= 1000000).
There are 10000 lines at most.
Output
For each n, output counting result in one line.
Sample Input
45
Sample Output
02
Hint
f(1) = 1, f(2) = f(3) = f(5) = 2, f(4) = 3.
Author: WU, Jun
Source: ZOJ Monthly, December 2009理论依据:
zoj的题目,对时间和空间的要求都很高。
这一题,首先做的时候,超时。
不看时间,不看数据,直接枚举,不超时是不可能。
根据的公式和上一题福州大学oj那一题是一样的。
贴一下超时代码吧,留个纪念。
1 //超时代码 2 3 #include4 #include 5 6 int f[1000003]; 7 int Num_Euler(int n) 8 { 9 int num=1,k,i;10 for(i=2;i*i<=n;i++)11 if(n%i==0)12 {13 k=1;14 while(n%i==0)15 {16 k++;17 n=n/i;18 }19 num=num*k;20 }21 if(n!=1)22 num=num*2;23 return num;24 }25 26 void make_ini()27 {28 int i;29 for(i=1;i<=1000000;i++)30 f[i]=Num_Euler(i);31 }32 int main()33 {34 int n,i,num;35 make_ini();36 while(scanf("%d",&n)>0)37 {38 num=0;39 for(i=1;i
后来想用筛选法来筛一次,然后求值。第一次写的时候,也错了。
1 void make_NumEuler()2 {3 int i,j,k;4 for(i=1;i<=1000000;i++)5 opl[i]=1;6 for(i=1;i<=len;i++)7 for(j=prime[i],k=2;j<=1000000;j=j+prime[i],k++)8 opl[j]=opl[j]*k;9 }
思路是有的,就是没有写出来,(⊙o⊙)…
最后的代码:1 #include2 #include