首页 > 其他分享 >CF2050F Maximum modulo equality 题解

CF2050F Maximum modulo equality 题解

时间:2024-12-06 21:53:53浏览次数:4  
标签:equality 200005 int 题解 kp 因数 CF2050F 同余于 同余

【题意简述】

你有一个长度为 \(n\) 的数组 \(a\)。

每一次询问给定 \(l,r\),寻找最大的 \(m\) 使得 \(a_l\) 到 \(a_r\) 的所有数对 \(m\) 同余,

【前置数学芝士】

首先是一个非常 Naive 的结论,请自行感性证明:设 \(a>b\),\(a\) 和 \(b\) 对 \(a-b\) 同余。

理性证明:

设 \(p=a-b\),\(a=kp+q\)

那么 \(b=a-(a-b)=a-p=(k-1)p+q\)

他们对 \(p\) 同余(都是 \(q\))

然后另一个非常 Naive 的结论,请自行感性证明:设 \(a>b\),\(a\) 和 \(b\) 对 \(a-b\) 的所有因数同余。

理性证明:

设 \(p=a-b\),\(a=kp+q\)\(p=a-b\),\(b=(k-1)p+q\)

设 \(p\) 的这个因数为 \(p_0\)

因为 \(kp\) 和 \((k-1)p\) 可以被 \(p\) 整除,所以这两个数也可以被 \(p_0\) 整除,同余于 \(p_0\)

而且 \(q\) 和 \(q\) 同余于 \(p_0\)

所以 \(a\) 和 \(b\) 的两部分分别同余于 \(p_0\)

所以 \(a\) 和 \(b\) 同余于 \(p_0\)

【思路】

首先 \(a_l\) 到 \(a_r\) 同余可拆分成:

限制 结论
\(a_l,a_{l+1}\) 同余 \(m\) 是 \(|a_l-a_{l+1}|\) 的因数
\(a_{l+1},a_{l+2}\) 同余 \(m\) 是 \(|a_{l+1}-a_{l+2}|\) 的因数
\(…\) \(…\)
\(a_{r-2},a_{r-1}\) 同余 \(m\) 是 \(|a_{r-2}-a_{r-1}|\) 的因数
\(a_{r-1},a_r\) 同余 \(m\) 是 \(|a_{r-1}-a_r|\) 的因数

然后就出结论了,\(m=\gcd(|a_l-a_{l+1}|,|a_{l+1}-a_{l+2}|,…,|a_{r-2}-a_{r-1}|,|a_{r-1}-a_r|)\)。

用 ST 表搞一搞,特判一下区间长度为 1。

【Code】

#include <bits/stdc++.h>
using namespace std;

int n,q,a[200005],s[200005];
int l,r,Log[200005];

struct ST_map{
	int Gcd[200005][21];
	void Init(){
		for(int i=1;i<=n-1;i++) Gcd[i][0]=s[i];
		for(int i=1;i<=20;i++){
			for(int j=1;j<=n-1;j++){
				Gcd[j][i]=__gcd(Gcd[j][i-1],Gcd[min(j+(1<<(i-1)),n)][i-1]);
			}
		}
	}
	int Query(int l,int r){
		int logx=Log[r-l+1];
		return __gcd(Gcd[l][logx],Gcd[r-(1<<logx)+1][logx]);
	}
}ST;

void Main(){
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<n;i++)  s[i]=abs(a[i+1]-a[i]);
	ST.Init();
	while(q--){
		scanf("%d%d",&l,&r);
		if(l==r) printf("0 ");
		else     printf("%d ",ST.Query(l,r-1));
	}puts("");
} 

int T;
int main()
{
	int cnt=0,last=2;
	for(int i=2;i<=200000;i++){
		if(i==last){
			cnt++;
			last*=2;
		}Log[i]=cnt;
	}
	scanf("%d",&T);
	while(T--) Main();
	return 0;
}

【后记】

祝贺我自己,在上蓝前的最后一场 Div.3 AK。

两发罚时全是数组开小,乐。

以后就打不了了。

标签:equality,200005,int,题解,kp,因数,CF2050F,同余于,同余
From: https://www.cnblogs.com/Sundar-2022/p/18591483

相关文章

  • P5007 DDOSvoid 的疑惑 题解
    题目传送门思路树形dp模版题。设\(dp_i\)为\(pos\)的最优解,\(dp2_i\)为只考虑\(pos\)子树时,毒瘤集的数量。可得:\(dp_i=dp_{i}\timesdp2_{son}+dp_{son}\timesdp2_{i}+dp_i+dp_{son}\)\(dp2_i=dp2_{i}\timesdp2_{son}+dp2_{i}+dp2_{son}\)用深搜来更新\(dp\)......
  • 题解:P1007 独木桥
    独木桥-洛谷https://www.luogu.com.cn/problem/P1007思路:输入部分:首先读取独木桥的长度 L 和初始留在桥上的士兵数目 N。然后通过循环读取每个士兵的初始坐标并存储在 soldiers 数组中。计算最小时间和最大时间:对于每个士兵,通过 min(soldiers[i],L+1-soldie......
  • 递归疑难问题解答
    1.计算一个数的每位之和(递归实现)写一个递归函数DigitSum(n),输入一个非负整数,返回组成它的数字之和例如,调用DigitSum(1729),则应该返回1+7+2+9,它的和是19输入:1729,输出:19#include<stdio.h>intfac(intn){ if(n<10) { returnn; } else { returnfac(n/10)+......
  • 题解:P3891 [GDOI2014] 采集资源
    P3891[GDOI2014]采集资源题意简述:开始时你有数量为\(m\)的资源,有\(n\)种“苦工”可以不限次数地建造,每种苦工都有一个花费\(a\),和一个效率\(b\),要求最小化资源数量到达\(t\)的时间Solution:我们考虑先对于每一种花费\(i\)最大化它的“单位时间内产生的资源的数量......
  • MQ消息乱序问题解析与实战解决方案
    1.背景在分布式系统中,消息队列(MQ)是实现系统解耦、异步通信的重要工具。然而,MQ消费时出现的消息乱序问题,经常会对业务逻辑的正确执行和系统稳定性产生不良影响。本文将详细探讨MQ消息乱序问题的根源,并提供一系列在实际应用中可行的解决方案。2.MQ消息乱序问题分析常见的MQ消息......
  • P7206 [COCI2019-2020#3] Lampice 题解
    显然可以对答案奇偶分别二分,判断用点分治。考虑对每个点记录到当前分治中心的路径正着和倒着的hash值,那么两个点之间的路径是回文路径可以用一个简单的式子表示,移项一下把跟一个点有关的值放到一边,用unordered_map记录/查询即可,需要卡常,时间复杂度\(\mathcalO(n\log^2n)\)。......
  • CCF-CSP真题 《201412_2_Z字形扫描》Python思路题解
    题目描述:在图像编码的算法中,需要将一个给定的方形矩阵进行 Z 字形扫描(ZigzagScan)。给定一个 n×n的矩阵,Z字形扫描的过程如下图所示:对于下面的 4×4 的矩阵,1539375694647313对其进行 Z 字形扫描后得到长度为 16 的序列:1539739547......
  • 2023年12月GESPC++二级真题解析
    一、单选题(每题2分,共30分)题目123456789101112131415答案CADDDADCDBCDCBB1.以下不可以做为C++变量的是()。A.FiveStarB.fiveStarC.5StarD.Star5【答案】C【考纲知识点】变量的定义与使用(二级考纲知识点范畴),具体涉及到变量名的命名规则。在C++语言中,变量名有严格......
  • BUUCTF Pwn jarvisoj_level2_x64 题解
    1.下载checksec64位用IDA64打开SHIFT+F12查找字符串找到了binsh函数里面也有system进主函数看看看到了栈溢出漏洞这是64位程序所以构造ROP链时要用rdi传参+用ret栈平衡找到这两个的地址:构造exp:运行得到flag  flag{4b1340f5-06be-4377-9630-fd2c77f016......
  • P9142 [THUPC 2023 初赛] 欺诈游戏 题解
    P9142[THUPC2023初赛]欺诈游戏题面这个游戏名叫《走私游戏》。游戏规则大概是这样的:一名玩家扮演走私者,一名玩家扮演检察官。走私者可以将\(x\)日元(\(x\)为\([0,n]\)内的整数,由走私者决定)秘密放入箱子中,而检查官需要猜测箱子中的金额。假设检察官猜了\(y\)(\(y\)也必......