首页 > 代码库 > HDU 2521 反素数
HDU 2521 反素数
反素数
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4238 Accepted Submission(s): 2456
Problem Description
反素数就是满足对于任意i(0<i<x),都有g(i)<g(x),(g(x)是x的因子个数),则x为一个反素数。现在给你一个整数区间[a,b],请你求出该区间的x使g(x)最大。
Input
第一行输入n,接下来n行测试数据
输入包括a,b, 1<=a<=b<=5000,表示闭区间[a,b].
输入包括a,b, 1<=a<=b<=5000,表示闭区间[a,b].
Output
输出为一个整数,为该区间因子最多的数.如果满足条件有多个,则输出其中最小的数.
Sample Input
3
2 3
1 10
47 359
Sample Output
2
6
240
这道题做了两次,第一次是没学数论的时候,然后学完数论又写了一次。
没学数论的时候,求一个数的约数,因为一个约数对应另一个约数,两个约数相乘即为该数,那么搜索时搜一半就行了,每搜到1个约数,总约数+2。
代码:
1 #include <stdio.h> 2 #include <math.h> 3 main() 4 { 5 int n, t, sum, a, b, num; 6 scanf("%d",&t); 7 while(t--) 8 { 9 scanf("%d %d",&a,&b);10 sum=0;11 int max=0;12 for(int i=a;i<=b;i++)13 {14 sum=0;15 for(int j=1;j<sqrt(i);j++)16 {17 if(i%j==0)18 sum+=2;19 }20 if(sqrt(i)*sqrt(i)==i) //若该数位平方数,那么中间一个+1就行了,+2就重复了 21 sum++;22 if(sum>max) 23 {max=sum;num=i;}24 }25 printf("%d\n",num);26 }27 }
学数论时候讲了个公式,一个数一定能这样表示:num=p1^e1*p2^e2*...*pn^en(p1....pn为该数的质因数),那么该数的约数总数sum=(1+e1)*(1+e2)*...*(1+en)。
那么这道题可以这样做了:
先把5000内的素数求出来,然后暴搜套公式答案就出来了。
代码:
1 #include <cstdio> 2 #include <iostream> 3 #include <algorithm> 4 #include <cstring> 5 #include <vector> 6 using namespace std; 7 8 int p[5005]; 9 int visited[5005];10 int tot;11 12 void init_p(){13 int i, j;14 tot=0;15 memset(visited,0,sizeof(visited));16 for(i=2;i<5005;i++){17 if(!visited[i]) p[tot++]=i;18 for(j=0;j<tot&&p[j]*i<5005;j++){19 visited[p[j]*i]=1;20 if(i%p[j]==0) break;21 }22 }23 }24 25 main()26 {27 int t;28 int i, j, a, b;29 int k, MIN, n, ans, kk;30 cin>>t;31 init_p();32 while(t--){33 scanf("%d %d",&a,&b);34 MIN=-1;35 for(i=a;i<=b;i++)36 {37 ans=1;n=i;38 for(j=0;j<tot;j++){39 if(p[j]>i) break;40 k=0;41 while(n%p[j]==0){42 n/=p[j];43 k++;44 }45 ans*=1+k;46 }47 if(ans>MIN) {kk=i;MIN=ans;}48 }49 printf("%d\n",kk);50 }51 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。