【题解】洛谷P1463 [POI2002][HAOI2007] 反素数（约数个数公式+搜索）

洛谷P1463：https://www.luogu.org/problemnew/show/P1463

思路

约数个数公式  

a_i为质因数分解的质数的指数

定理：

设m=2^a1*3^a2*...*p^ak（其中p为第k大的质数）是Antiprime数 则必有a1≥a2≥a3≥...≥ak≥0

因此如果有两个值约数个数相同 则要取值比较小的那个

剪枝：

有了这个定理我们就可以搜索质数的指数 由于2³¹已经远远超过数据规模 因此我们只需要搜到31层质因子的个数最多只有10个（所有质因子相乘得到他们可以凑成的最大值）

代码

#include<iostream> using namespace std; int a[20]={0,2,3,5,7,11,13,17,19,23,29};//打表出前10个质数 long long n,s,s1; void search(long long x,long long y,long long b,long long z) { if(x==11) return;//第二个剪枝 long long k=1; for(int i=1;i<=b;i++)//枚举每个质因子的范围 { k*=a[x];//当前质因子有k个相乘 if(y*k>n) return;//超过范围就跳出 if(z*(i+1)==s1&&y*k<s) s=y*k;//如果两个值约数相等 取小的那个 if(z*(i+1)>s1)//如果大于它 取大的那个 { s1=z*(i+1); s=y*k; } search(x+1,y*k,i,z*(i+1)); } } int main() { cin>>n; search(1,1,31,1); //分别为质因子个数 ans 指数层数 约数个数 cout<<s; } View Code

 

转载于:https://www.cnblogs.com/BrokenString/p/9656479.html

相关资源：JAVA上百实例源码以及开源项目