【题解】洛谷P1463 [POI2002][HAOI2007] 反素数(约数个数公式+搜索)
2024-08-27 14:07:30
洛谷P1463:https://www.luogu.org/problemnew/show/P1463
思路
约数个数公式
ai为质因数分解的质数的指数
定理:
设m=2a1*3a2*...*pak(其中p为第k大的质数)是Antiprime数 则必有a1≥a2≥a3≥...≥ak≥0
因此如果有两个值约数个数相同 则要取值比较小的那个
剪枝:
- 有了这个定理我们就可以搜索质数的指数 由于231已经远远超过数据规模 因此我们只需要搜到31层
- 质因子的个数最多只有10个(所有质因子相乘得到他们可以凑成的最大值)
代码
#include<iostream>
using namespace std;
int a[]={,,,,,,,,,,};//打表出前10个质数
long long n,s,s1;
void search(long long x,long long y,long long b,long long z)
{
if(x==) return;//第二个剪枝
long long k=;
for(int i=;i<=b;i++)//枚举每个质因子的范围
{
k*=a[x];//当前质因子有k个相乘
if(y*k>n) return;//超过范围就跳出
if(z*(i+)==s1&&y*k<s)
s=y*k;//如果两个值约数相等 取小的那个
if(z*(i+)>s1)//如果大于它 取大的那个
{
s1=z*(i+);
s=y*k;
}
search(x+,y*k,i,z*(i+));
}
}
int main()
{
cin>>n;
search(,,,); //分别为质因子个数 ans 指数层数 约数个数
cout<<s;
}
最新文章
- android studio 应用小知识总结
- Dynamic Invok Webservice
- 【原创】CHROME 最小字体限制为12PX的终极解决方案
- 护肤品总结 Skin Care (2)
- mysql去重的最方便的两种方法
- Python之路: socket篇
- 【2017-03-20】HTML基础知识、文字标记、图片标记、空格换行、表格、表格嵌套及布局、超链接
- Blockly编程:用Scratch制作游戏愤怒的小牛(小鸟)
- IEEE Trans 2007 Signal Recovery From Random Measurements via OMP
- 关于metaclass,我原以为我是懂的
- UNIX网络编程——UDP 中的外出接口的确定
- postman的安装与使用(模拟请求)
- Vue slot插槽内容分发
- String 和StringBuffer的简单实用案例
- 安装pod
- spring事务没回滚
- [转帖]Cgroups 与 Systemd
- 【bzoj4448】SCOI2015 情报传递
- Codeforces Round #425 (Div. 2) Misha, Grisha and Underground(LCA)
- Git系列四之在本地服务器搭建gitlab仓库管理