文档章节

洛谷P1221 最多因子数 [搜索,数学]

o
 osc_1ee7cxmx
发布于 2018/08/06 19:25
字数 677
阅读 7
收藏 0

精选30+云产品,助力企业轻松上云!>>>

  题目传送门

最多因子数

目描述

数学家们喜欢各种类型的有奇怪特性的数。例如,他们认为945是一个有趣的数,因为它是第一个所有约数之和大于本身的奇数。

为了帮助他们寻找有趣的数,你将写一个程序扫描一定范围内的数,并确定在此范围内约数个数最多的那个数。不幸的是,这个数和给定的范围的都比较大,用简单的方法寻找可能需要较多的运行时间。所以请确定你的算法能在几秒内完成最大范围内的扫描。

输入输出格式

输入格式:

 

只有一行,给出扫描的范围,由下界L和上界U确定。满足2≤L≤U≤1000000000。

 

输出格式:

 

对于给定的范围,输出该范围内约数个数D最多的数P。若有多个,则输出最小的那个。请输出“Between L and U,P has a maximum of D divisors.”,其中L,U,P和D的含义同前面所述。

 

输入输出样例

输入样例#1: 
1000 2000
输出样例#1: 
Between 1000 and 2000, 1680 has a maximum of 40 divisors.


  分析:

  一道比较考验思维的搜索题。

  直接一个个暴搜肯定不行,但是如果把一个数因数分解的话,$10^9$以内最多不会超过30个,那么我们可以考虑搜索质因子。把一个数表示成质因数幂的形式为:

  $A=x_1^{p_1}*x_2^{p_2}*x_3^{p_3}*...*x_n^{p_n}$

  则该数的约数个数为$(p_1+1)*(p_2+1)*(p_3+1)*...*(p_n+1)$,根据这个公式来检验当前答案是否最优。

  不过要注意,数据中一个点131074会出锅,因为131074分解质因数是2×65537,我们搜索的时候只考虑100以内的质数(否则会T),所以需要特判一下。

  当然这种做法很轻松就可以Hack掉,不过数据很水就是了(逃。

  Code:

//It is made by HolseLee on 6th Aug 2018
//Luogu.org P1221
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
ll L,R,ans,tot,c[27];
ll s[27]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,91,97};

inline void check(ll sum)
{
    ll ret=1;
    for(int i=1;i<=26;++i)ret*=(c[i]+1);
    if(ret>tot)tot=ret,ans=sum;
    if(ret==tot)ans=min(sum,ans);
}

inline void dfs(ll sum,int sta)
{
    if(sum>R)return;
    if(sum>=L&&sum<=R)check(sum);
    for(int i=sta;i<=26;++i){
        ++c[i];
        dfs(sum*s[i],i);
        --c[i];
    }
}

int main()
{
    scanf("%lld%lld",&L,&R);
    if(L==R&&L==131074){
        printf("Between %lld and %lld, %lld has a maximum of 4 divisors.",L,R,L);
        return 0;
    }
    dfs(1,1);
    printf("Between %lld and %lld, %lld has a maximum of %lld divisors.",L,R,ans,tot);
    return 0;
}

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

Java线程池

前言 Java中对线程池的抽象是ThreadPoolExecutor类,Executors是一个工具类,内置了多种创建线程池的方法: newFixedThreadPool:固定长度线程池 newCachedThreadPool :可缓存线程池 newSin...

nullpointerxyz
28分钟前
35
0
Python笔记:用Python制作二维码

这些年,二维码在我国的日常使用频率特别大。因为其具有简单及安全性吧!除了用网络工具制作二维码,其实用JavaScript或Python也可以制作二维码,而且更有个性。 示例一(制作普通黑白二维码...

tengyulong
40分钟前
0
0
Redis-初体验/数据结构

定义: Redis 是 C 语言开发的一个开源的(遵从 BSD 协议)高性能键值对(key-value)的内存数据库,可以用作数据库、缓存、消息中间件等。它是一种 NoSQL(not-only sql,泛指非关系型数据库...

心田已荒
43分钟前
15
0
如何在保留订单的同时从列表中删除重复项? - How do you remove duplicates from a list whilst preserving order?

问题: Is there a built-in that removes duplicates from list in Python, whilst preserving order? 是否有内置的程序在保留顺序的同时从Python列表中删除重复项? I know that I can us...

fyin1314
今天
29
0
以太坊智能合约开发常见的10个安全问题

本文介绍CheckMarx安全研究小组通过扫描公开的以太坊智能合约所发现的Solidity智能合约开发中常见的十大安全问题,其中__未检查的外部调用__ 和 高成本循环 分列排行榜前两名。该安全问题排行...

区块链教程
今天
19
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部