洛谷 P1463 [HAOI2007]反素数
2024-09-01 23:30:42
https://www.luogu.org/problemnew/show/P1463
注意到答案就是要求1-n中约数最多的那个数(约数个数相同的取较小的)
根据约数个数的公式,在约数个数相同的情况下,如果各个质因子是从2开始的连续质数且指数不下降,那么一定可以得到最小的结果
玄学爆搜即可。。。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<bitset>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
const ll N=;
ll n;
ll prime[],len;
pll ans;
bool nprime[];
void dfs(ll x,ll k,ll p,ll maxn)
{
if(ans.se<k||(ans.se==k&&ans.fi>x)) ans=pll(x,k);
if(maxn==) return;
ll i,now=;
for(i=;i<=maxn;i++)
{
if(now*x>n) break;
dfs(now*x,k*(i+),p+,i);
now*=prime[p];
}
}
int main()
{
ll i,j;
scanf("%lld",&n);
for(i=;i<=N;i++)
{
if(!nprime[i]) prime[++len]=i;
for(j=;j<=len&&i*prime[j]<=N;j++)
{
nprime[i*prime[j]]=;
if(i%prime[j]==) break;
}
}
dfs(,,,);
printf("%lld",ans.fi);
return ;
}
最新文章
- 无法识别的属性“targetFramework”的解决方法
- vertical-align属性
- Flex 文本控件实现自定义复制粘贴
- DOM操作 append prependTo after before
- UVA 10635 Prince and Princess
- hadoop学习记录(三)HBase基本概念
- SDC(5)&ndash;FPGA系统级同步输入的约束
- Port 8081 already in use, packager is either not running or not running correctly
- &#39;k1&#39;: 大于66的所有值, &#39;k2&#39;: 小于66的所有值
- 在html后面拼接字符串后页面的跳转
- 删除pending.xml
- centos7下安装docker(17docker监控---docker自带监控命令)
- jq 切换功能toggle
- MD5=======RBAC权限管理
- ubuntu12.04安装squid
- P2422 良好的感觉
- Dom4j中getStringValue()和getText()用法的区别
- es6学习笔记3--解构和对象
- linux驱动之LCD(无framebuffer)
- SSH Secure File Transfer Client连接远程设备报“algorithm negotiation failed”错的解决方法