首页 > 代码库 > 数学题
数学题
1053: [HAOI2007]反素数ant
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 2872 Solved: 1639
[Submit][Status][Discuss]
Description
对于任何正整数x，其约数的个数记作g(x)。例如g(1)=1、g(6)=4。如果某个正整数x满足：g(x)>g(i) 0<i<x
，则称x为反质数。例如，整数1，2，4，6等都是反质数。现在给定一个数N，你能求出不超过N的最大的反质数么
？
Input
一个数N（1<=N<=2,000,000,000）。
Output
不超过N的最大的反质数。
Sample Input
1000
Sample Output
840
//这个数学题有意思，本来求约数个数，就是一个数的质数个数乘啊乘的，不难，
举个例子，60 = 2*2*3*5 根据排列组合，约数个数就是 3*2*1=6 因为不选(即0)也是一种选择
但是求范围内的最大的反质数，数据太大，循环太慢，
就只能逆向思维一下了，用质数去组合，组成小于这个数，且约数最大的，且最小的(就是没读懂题意，要输出最小的，才没做出这个题)，
然后,质数必定会连续，因为不连续 一定有更小的数约数和这个数相等，例如 2*3*7 , 2*3*5 就更小，且约数相同
懂了就简单了
0ms
1 #include <stdio.h> 2 typedef long long LL; 3 4 const int p[12]={2,3,5,7,11,13,17,19,23,29,31,37};//全部有一个就大于20E这个数据范围了 5 LL n,ans,m_yue; 6 7 void dfs(int dep,LL num,LL yue) 8 { 9 if (dep>=12) return;10 if (yue>m_yue)11 {12 ans=num;13 m_yue=yue;14 //printf("??? %lld\n",ans);15 }16 if (m_yue==yue&&num<ans) ans=num;17 for (int i=1;i<=50;i++)//i 代表多少次方18 {19 if (num*p[dep]>n) break;20 dfs(dep+1,num*=p[dep],yue*(i+1));21 }22 }23 24 int main()25 {26 scanf("%lld",&n);27 ans=1,m_yue=1;28 dfs(0,1,1);//深度，数字，约数个数29 printf("%lld\n",ans);30 return 0;31 }
数学题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。