F——RGCDQ (HDU 5317)

简介:

点击打开链接

Problem Description

Mr. Hdu is interested in Greatest Common Divisor (GCD). He wants to find more and more interesting things about GCD. Today He comes up with Range Greatest Common Divisor Query (RGCDQ). What’s RGCDQ? Please let me explain it to you gradually. For a positive integer x, F(x) indicates the number of kind of prime factor of x. For example F(2)=1. F(10)=2, because 10=2*5. F(12)=2, because 12=2*2*3, there are two kinds of prime factor. For each query, we will get an interval [L, R], Hdu wants to know maxGCD(F(i),F(j))(L≤i<j≤R)
 

Input
There are multiple queries. In the first line of the input file there is an integer T indicates the number of queries.
In the next T lines, each line contains L, R which is mentioned above.

All input items are integers.
1<= T <= 1000000
2<=L < R<=1000000
 

Output
For each query,output the answer in a single line.
See the sample for more details.
 

Sample Input
 
 
2 2 3 3 5
 

Sample Output
 
 
1 1
 
题目大意:

对1~10^6的每个数进行素因子分解,不同素因子的个数作就是它的 f 函数 值,比如12=2^2*3,则f(12)=2,求出它们的 f 函数值之后,给定T组数据,每组数据有一个区间[L,R],问区间任意两个不同下标的数maxGCD(F(i),F(j)) (L≤i<j≤R),他们的GCD值最大为多少


解题思路:

首先我们要求一下从 1 - 10^6中对应的 f 函数值,求出函数值之后我们再考虑怎么做,首先观察一下数据范围,10^6*T,肯定会超时,所以我们要想一个 O(1)的算法,我们又观察了一下, 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 > 10^6,所以GCD最大值就是7,也就是说我们可以通过一个DP[i][j] ,表示前 i 个 f 值中有多少个 j,也就是用DP的思想来做这个题(DP并不是很会) ,而这个DP[10^6+5][8]

<span style="font-size:18px;">#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int MAXN = 1e6+5;
const int INF = 2e9+5;
typedef long long LL;
int f[MAXN];

void Init()
{
    memset(f, 0, sizeof(f));
    for(int i=2; i<MAXN; i++)
    {
        if(!f[i])
        {
            for(int j=i; j<MAXN; j+=i)
                f[j]++;
        }
    }
}

int dp[MAXN][8];
void Pre()
{
    memset(dp, 0, sizeof(dp));
    dp[2][1] = 1;
    for(int i=3; i<MAXN; i++)
    {
        for(int j=1; j<8; j++)
        {
            dp[i][j] = dp[i-1][j];
        }
        dp[i][f[i]]++;
    }
}
int main()
{
    ///cout<<2*3*5*7*11*13*17*19<<endl;
    Init();
    Pre();
    int T, L, R;
    ///cin>>T;
    scanf("%d",&T);
    while(T--)
    {
        int ret = -INF;
        ///cin>>L>>R;
        scanf("%d%d",&L,&R);
        for(int i=1; i<8; i++ )
        {
            if(dp[R][i]-dp[L-1][i]>1 && dp[R][i])
                ret = max(ret, i);
        }
        cout<<ret<<endl;
    }
    return 0;
}</span>


目录
相关文章
|
10月前
|
搜索推荐 数据可视化 大数据
构建医院随访系统:模块化设计与核心功能开发实践
医院随访系统以患者为中心,集成随访计划制定、多方式随访、智能提醒、数据统计分析等功能,实现诊后全流程管理。系统支持与HIS对接,提供个性化随访模板、自动预警、满意度调查及医德考评,提升医疗质量与患者满意度,优化资源利用。
528 1
|
机器学习/深度学习 人工智能 算法
图解机器学习 | KNN算法及其应用
KNN算法(K近邻算法)是一种很朴实的机器学习方法,既可以做分类,也可以做回归。本文详细讲解KNN算法相关的知识,包括:核心思想、算法步骤、核心要素、缺点与改进等。
5265 1
图解机器学习 | KNN算法及其应用
|
9月前
|
存储 运维 自然语言处理
OpenClaw阿里云上一键部署上云指南,让OpenClaw(原Clawdbot)24小时为你工作
OpenClaw(原Clawdbot、Moltbot)是一款开源AI自动化代理平台,核心依托大语言模型的自然语言理解能力,无需用户掌握编程技能,仅通过日常语言指令即可完成办公自动化、文件管理、多工具协同、基础开发辅助等多元任务,兼容主流大语言模型,可灵活对接各类应用接口与私有知识库,适配个人办公、轻量团队协作等多种场景。2026年,阿里云轻量服务器针对OpenClaw优化推出专属一键部署方案,通过预置应用镜像,跳过手动配置依赖、调试运行环境的复杂步骤,大幅降低部署门槛,同时依托云端基础设施实现7×24小时不间断运行,让OpenClaw持续为用户处理自动化任务,兼顾便捷性、稳定性与低成本,成为个
936 9
|
云安全 人工智能 搜索推荐
客户案例|皇家宠物食品:以“懂我”的温暖服务,延续每一份人宠羁绊
皇家宠物食品携手阿里云与Salesforce,打造高性能本地化客户关怀平台,实现多渠道服务整合,为宠主提供个性化、温暖的服务体验,助力科学养宠新时代。
|
人工智能 自然语言处理 运维
【新模型速递】PAI-Model Gallery云上一键部署Qwen3-Coder模型
Qwen3-Coder 是通义千问最新开源的 AI 编程大模型正式开源,拥有卓越的代码和 Agent 能力,在多领域取得了开源模型的 SOTA 效果。PAI 已支持最强版本 Qwen3-Coder-480B-A35B-Instruct 的云上一键部署。
|
10月前
|
人工智能 监控 数据挖掘
智能体来了(西南总部)拆解:AI Agent 指挥官 如何通过 Coze 工作流调度 AI 调度官
随着大模型深入业务执行层,AI Agent亟需系统化协同。本文提出“指挥官+调度官”分层机制:指挥官负责目标拆解与策略决策,调度官专注执行编排与资源管控,依托COZE工作流实现解耦协同,提升可控性、可解释性与跨场景扩展能力。
608 1
|
9月前
|
人工智能 自然语言处理 JavaScript
一分钟部署OpenClaw(Clawdbot)+问题解答,最爽的一键启动!
OpenClaw(前身为 Clawdbot、Moltbot)是一款开源 AI 代理与自动化平台,具备自然语言控制、任务自动化执行、多模型兼容等核心能力,可实现文件处理、邮件管理、日程规划、多工具协同等多样化功能,堪称 “专属数字员工”。2026 年阿里云推出的轻量应用服务器一键部署方案,通过预置专属镜像简化了复杂的环境配置流程,无需专业技术储备,零基础用户也能快速完成部署,实现 7×24 小时不间断运行。本文将详细拆解部署全流程,并针对性解读常见问题与解决方案,全程无营销表述,严格遵循技术文档核心逻辑。
1530 4
|
SQL 关系型数据库 MySQL
菜鸟之路Day30一一MySQL之DML&DQL
本文介绍了MySQL中DML(数据操作语言)和DQL(数据查询语言)的核心用法。DML主要包括插入(insert)、更新(update)和删除(delete)语句,通过具体示例演示了如何对表数据进行增删改操作。DQL则聚焦于数据查询,涵盖基本查询、条件查询、聚合函数、分组查询、排序查询和分页查询等内容。文章通过丰富的SQL语句实例,帮助读者掌握如何高效查询和操作数据库中的数据,适合初学者学习和实践。
860 12
|
10月前
|
监控 安全 网络安全
什么是SSL证书?
SSL(安全套接层)是保障网站数据传输安全的加密协议,通过HTTPS和锁形图标建立用户信任。它验证网站身份、防止信息窃取,影响SEO与访问安全。现代多采用更安全的TLS协议。
1062 0
|
11月前
|
消息中间件 Dubbo Java
深挖红黑树底层原理
深入解析红黑树底层原理,涵盖定义、特性、旋转与插删操作,结合Java源码实现及阿里生产实践,全面掌握高频面试与实战核心要点。