博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
zoj 3286 Very Simple Counting---统计[1,N]相同因子个数
阅读量:5750 次
发布时间:2019-06-18

本文共 2348 字,大约阅读时间需要 7 分钟。

Very Simple Counting

Time Limit: 1 Second     
Memory Limit: 32768 KB

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 #include
4 #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 #include
2 #include
3 #include
4 #include
5 #include
6 7 using namespace std; 8 9 10 bool s[1000003];11 int num[1000003];12 int ans[1000003];//个数13 int f[1000003];14 map
Q;15 16 17 void make_ini()18 {19 int i,j,k;20 for(i=1;i<=1000000;i++)21 {22 num[i]=i;23 ans[i]=1;24 f[i]=0;25 }26 for(i=2;i<=1000000;i++)27 if(s[i]==false)//是素数28 {29 for(j=i;j<=1000000;j=j+i)//枚举每个素数的倍数30 {31 // if(j%i==0) //这个肯定成立,不需要32 {33 k=1;34 while(num[j]%i==0)35 {36 num[j]=num[j]/i;37 k++;38 }39 ans[j]=ans[j]*k;40 }41 s[j]=true;42 }43 }44 for(i=1;i<=1000000;i++)45 {46 k=ans[i];47 if(Q.find(k)==Q.end())48 {49 Q[k]=1;50 }51 else Q[k]++;52 f[i]=Q[k];53 }54 }55 56 int main()57 {58 int n;59 make_ini();60 // Q.clear();61 while(scanf("%d",&n)>0)62 {63 printf("%d\n",f[n]-1);64 }65 return 0;66 }

 

转载于:https://www.cnblogs.com/tom987690183/p/3250338.html

你可能感兴趣的文章
hiveserver2修改线程数
查看>>
XML教程
查看>>
oracle体系结构
查看>>
Microsoft Exchange Server 2010与Office 365混合部署升级到Exchange Server 2016混合部署汇总...
查看>>
Proxy服务器配置_Squid
查看>>
开启“无线网络”,提示:请启动windows零配置wzc服务
查看>>
【SDN】Openflow协议中对LLDP算法的理解--如何判断非OF区域的存在
查看>>
纯DIV+CSS简单实现Tab选项卡左右切换效果
查看>>
栈(一)
查看>>
ios 自定义delegate(一)
查看>>
创建美国地区的appleId
查看>>
例题10-2 UVa12169 Disgruntled Judge(拓展欧几里德)
查看>>
JS 原生ajax写法
查看>>
Composer管理PHP依赖关系
查看>>
React.js学习笔记之JSX解读
查看>>
我所了解的Libevent和SEDA架构
查看>>
Socket编程问题小记
查看>>
基于Flask-Angular的项目组网架构与部署
查看>>
一张图道尽程序员的出路
查看>>
redis 常用命令
查看>>