[bzoj]1053反质数<暴搜>

2018-06-17 22:13:12来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

题目:http://www.lydsy.com/JudgeOnline/problem.php?id=1053

感想:这道题拿到以后还是想去知道一个数的约数个数要怎么求,去网上搜了公式,但是还是没有思路,最后看了好几个大佬的博客我才勉强知道这道题怎么做

  其实我看见这数据范围我就下意识觉得搜索会爆,但是实际上这道题不会爆的

方法:首先约数的个数求法

  已知数n=2^a + 3^b + 5^c + 7^d +……+ 第i个素数^x

  约数个数=(a+1)*(b+1)*(c+1)*(d+1)*……*(x+1)

  在知道这个公式后就可以用暴搜了,但是还是要知道就是数据范围内,素数最多就12个,所以预处理前几个素数

  还是看代码吧,我在代码中加了一些注释

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<cstdlib>
 6 #include<cmath>
 7 #define maxn 2000000005
 8 using namespace std;
 9 
10 const int prime[20]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47};
11 
12 int n,m,ans,ans_tot;
13 
14 //设一个数n=2^a + 3^b + 5^c + 7^d +……+ prime[dep]^x;
15 //则这个数的约数个数为(a+1)*(b+1)*(c+1)*(d+1)*……*(x+1)
16 //这是约数个数计算公式 
17 
18 void fuck(int dep,long long now_val,int tot,int num)
19 {
20 //dep=当前是prime中的素数的下标
21 //now_val是当前的值
22 //tot指当前的约数的个数
23 //num是上一个素数(prime[dep-1])的幂 
24     if(dep==11) 
25     {
26         if(now_val>ans&&tot>ans_tot){
27             ans=now_val;ans_tot=tot;
28         }//当发现比ans还大的数且这个数的约数个数比ans多
29         //即找到一个更优的解
30         if(now_val<=ans&&tot>=ans_tot)
31         {
32             ans=now_val;ans_tot=tot;
33         } //当发现一个比ans小但是约数比ans多的数
34         //说明ans不是一个反素数,也可以更新答案
35         return; 
36         
37     }
38     int t=1;
39     for(int i=0;i<=num;i++)
40     {
41         fuck(dep+1,now_val*t,tot*(i+1),i);
42         //搜下一个素数,又i从0次方开始的,所以now_val*s,s=1;
43         //约数的公式可以知道这是tot*(i+1) 
44         //到这个时候,prime[dep]已经i次方了,所以幂是i 
45         //其实可以想到最优解是小素数的幂越大越优,所以加num限定 
46         t*=prime[dep];//t表示当前素数prime[dep]的i次方 
47         if(now_val*t>n)break;//当乘不下去了就跳出 
48         
49     }
50     
51 }
52 
53 int main()
54 {
55     scanf("%d",&n);
56     fuck(1,1,1,30);
57     printf("%d",ans);
58 }

以上皆为看了大佬博客后的理解,如有不对,请大佬们指出

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:自制贪吃蛇——方向控制,初始长度增加

下一篇:P1888 三角函数