MT3051 区间gcd

思路:

ST表,ST表模板可参考MT3024 max=min

注意,这里使用快读快写避免超时

代码:

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n, m, a[N], mn[N][20], Lg[N], l, r, ans;
void pre()
{
    Lg[1] = 0;
    for (int i = 2; i <= n; i++)
    {
        Lg[i] = Lg[i >> 1] + 1;
    }
}
void ST_create()
{ // 创建ST表
    for (int i = 1; i <= n; i++)
    {
        mn[i][0] = a[i];
    }
    for (int j = 1; j <= Lg[n]; j++)
    {
        for (int i = 1; i <= n - (1 << j) + 1; i++)
        {
            mn[i][j] = gcd(mn[i][j - 1], mn[i + (1 << (j - 1))][j - 1]);
        }
    }
}
int ST_qgcd(int l, int r)
{ // ST表求gcd
    int k = Lg[r - l + 1];
    return gcd(mn[l][k], mn[r - (1 << k) + 1][k]);
}
// 快读快写:
int read()
{
    int ret = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9')
        ch = getchar();
    while (ch >= '0' && ch <= '9')
    {
        ret = ret * 10 + ch - '0';
        ch = getchar();
    }
    return ret;
}
void write(int x)
{
    if (x >= 10)
        write(x / 10);
    putchar(x % 10 + '0');
}
int main()
{
    n = read(), m = read();
    for (int i = 1; i <= n; i++)
        a[i] = read();
    pre();
    ST_create();
    while (m--)
    {
        l = read(), r = read();
        ans = ST_qgcd(l, r);
        write(ans);
        putchar('\n');
    }
    return 0;
}

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/680862.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

python中的循环语句

while循环 基本语法格式 while 条件&#xff1a; 循环体 条件为真&#xff0c;则执行循环体代码 条件为假&#xff0c;则结束循环 打印 1-10的整数 死循环有时候也是必须的&#xff0c; while语句的语法&#xff1a; &#xff08;1&#xff09;变量的初始化&#xff0c;…

Clo3D导出服装动画,使用Unity3D展示

1.前言 Clo3D是一款应用于时装行业的3D服装设计软件,其强大的布料模拟算法可在3D空间中实现设计、制版、试衣和走秀,大幅提升数字作品逼真度和制作效率。为了让服装动画效果展示在Unity3D上模拟效果&#xff0c;需要Clo3D模拟出逼着的衣服动画。总体流程为Clo3D - Mixamo -Blen…

The 18th Northeast Collegiate Programming Contest(5/9/13)

心得 赛中ac&#xff1a;5&#xff0c;目前ac&#xff1a;9&#xff0c;题目总数&#xff1a;13 中档可做题还是很多的&#xff0c;可惜遇到了难绷的queueforces&#xff0c; 最后15min才判出来&#xff0c;oi赛制5wa4遗憾离场&#xff0c;赛后把几个题都给调过了&#xff0…

遗传算法+神经网络!基于遗传-神经网络(GA-BP)算法的光伏出力预测程序代码!

前言 准确地预测光伏发电出力对于电力系统运营和稳定性至关重要。随着预测技术的不断进步&#xff0c;越来越多的研究者逐渐意识到遗传算法在优化神经网络在新能源出力预测中的潜力。遗传算法是一种模拟生物进化过程的优化算法&#xff0c;通过不断迭代和选择&#xff0c;搜索…

期望18K,4年前端Cvte 视源股份一面挂

一面 1、自我介绍&#xff1f;毕业的时候一直在 xx 公司&#xff0c;你基本都在做什么项目&#xff1f; 2、你讲一下你主要负责哪一块的&#xff1f;balabala 3、你们的 json 是怎么定义组件间的联动的&#xff1f; 4、怎么确定区分两个 input&#xff1f; 5、你们是怎么触…

聚观早报 | 苹果预热WWDC24;怪兽充电第一季度营收

聚观早报每日整理最值得关注的行业重点事件&#xff0c;帮助大家及时了解最新行业动态&#xff0c;每日读报&#xff0c;就读聚观365资讯简报。 整理丨Cutie 6月5日消息 苹果预热WWDC24 怪兽充电第一季度营收 vivo Watch GT设计细节 长城汽车关闭欧洲总部 小米MIX Flip将…

电商架构浅析

前言 什么是电商&#xff0c;电商有哪些分类&#xff0c;以及一个完整的电商平台应该由哪些模块组成&#xff1f;本文将围绕电商平台系统的整体架构展开分析。 一、简介 1. 什么是电商 简单说就是通过网络进行的商务活动。以前的人都是通过现金进行交易&#xff0c;就是所谓的…

热贡文化旅游APP的设计与实现-计算机毕业设计源码69932

摘 要 21世纪的今天&#xff0c;随着社会的不断发展与进步&#xff0c;人们对于信息科学化的认识&#xff0c;已由低层次向高层次发展&#xff0c;由原来的感性认识向理性认识提高&#xff0c;管理工作的重要性已逐渐被人们所认识&#xff0c;科学化的管理&#xff0c;使信息存…

专业开放式耳机什么牌子更好?六大技巧教你不踩坑!

相信很多入坑的朋友再最开始挑选耳机的时候都会矛盾&#xff0c;现在市面上这么多耳机&#xff0c;我该怎么选择&#xff1f;其实对于开放式耳机&#xff0c;大家都没有一个明确的概念&#xff0c;可能会为了音质的一小点提升而耗费大量的资金&#xff0c;毕竟这是一个无底洞。…

LabVIEW源程序安全性保护综合方案

LabVIEW源程序安全性保护综合方案 一、硬件加密保护方案 选择和安装硬件设备 选择加密狗和TPM设备&#xff1a;选择Sentinel HASP加密狗和支持TPM&#xff08;可信平台模块&#xff09;的计算机主板。 安装驱动和开发工具&#xff1a;安装Sentinel HASP加密狗的驱动程序和开发…

在加拿大寻求2亿美元融资!Xanadu的CEO有话要说

内容来源&#xff1a;量子前哨&#xff08;ID&#xff1a;Qforepost&#xff09; 文丨慕一/娴睿 排版丨沛贤 深度好文&#xff1a;1500字丨5分钟阅读 摘要&#xff1a;加拿大光量子计算头部企业Xanadu希望在加拿大筹集1-2亿美元&#xff0c;用于建立量子数据中心。虽然融资不…

编译和运行qemu-uboot-arm64单板的Armbian系统

这篇文章ARM虚拟机安装OMV-CSDN博客遗留一个启动qemu-uboot-arm64单板Armbian镜像的问题&#xff0c;使用官方下载的镜像&#xff0c;会报错&#xff1a; fatal: no kernel available .... Failed to load /vmlinuz ...... qemu-system-aarch64 -smp 8 -m 8G -machine virt …

绿联Nas docker 中 redis 老访问失败的排查

部署了一些服务&#xff0c;老隔3-5 天其他服务就联不上 redis 了&#xff0c;未确定具体原因&#xff0c;只记录观察到的现象 宿主机访问 只有 ipv6 绑定了&#xff0c;ipv4 绑定挂掉了 其他容器访问 也无法访问成功 当重启容器后&#xff1a; 一切又恢复正常。 可能的解…

批量修改文件

最近几个月的文章都直接发在公众号上&#xff0c;没有同步到博客上&#xff0c;想去同步时发现已经有不少了&#xff0c;一个个修改太麻烦了。 之前没规划好&#xff0c;所以博客文章都是直接放在仓库一个目录下&#xff0c;数量多了之后&#xff0c;有点乱&#xff0c;不好管…

如何成为人工智能(AI)产品经理

AI产品 经理出现的历史背景 首先&#xff0c;我们需要从一个大的历史背景和趋势上来思考&#xff1a;为什么会有AI产品经理这样一个岗位。 AlphaGo先后打败了李世石、柯洁之后&#xff0c;大家都觉得AI好像已经成熟了。 但其实&#xff0c;AI之所以能发展到现在这样一个阶段…

C++ STL map容器erase操作避坑

map容器的erase方法有三种重载形式&#xff1a; //1.删除迭代器所指向的元素 //返回值是指向下一个节点的迭代器 iterator erase(iterator it); //2.区间删除 iterator erase(iterator first, iterator last); //3.根据键值删除 //返回值为删除的元素个数 size_type erase(con…

Windows下载安装RabbitMQ客户端(2024最新篇)

文章目录 RabbitMQ认知RabbitMQ下载RabbitMQ安装 更多相关内容可查看 RabbitMQ认知 定义&#xff1a;RabbitMQ是一个消息中间件&#xff0c;它接受并转发消息。你可以把它当做一个快递站点&#xff0c;当你要发送一个包裹时&#xff0c;你把你的包裹放到快递站&#xff0c;快递…

【CTF MISC】XCTF GFSJ0155 simple_transfer Writeup(流量分析+文件提取)

simple_transfer 文件里有flag&#xff0c;找到它。 解法 用 wireshark 分析&#xff0c;大部分都是 TCP 协议。 打开协议分级统计&#xff0c;有个 DLEP 占了 94.2% 的数据。 作为过滤器使用。全都是 Unknown。 用 binwalk 扫描。 binwalk f9809647382a42e5bfb64d7d447b409…

【C++小知识】为什么C语言不支持函数重载,而C++支持

为什么C语言不支持函数重载&#xff0c;而C支持 编译链接过程函数名修饰过程总结 在了解C函数重载前&#xff0c;如果对文件的编译与链接不太了解。可以看看我之前的一篇文章&#xff0c;链接: 文件的编译链接 想要清楚为什么C语言不支持函数重载而C支持&#xff0c;有俩个过程…

svg使用 element plus 使用外部下载的svg,使用或作为背景图片的使用方式,svg背景填充自适应父级宽高

friger.vue 注意&#xff1a;引入路径后加#svgView(preserveAspectRatio(none))&#xff0c;可解决宽高设置无效的问题 代码上就这两句就行&#xff0c;它去这个路径下去找/assets/svgs/login-bg.svg&#xff0c;往这个目录下放svg文件就行<template><div class&quo…