安阳汤阴县网站建设,上哪里建设个人网站,网站建设公司未来方向,高端小程序建设公司Powered by:NEFU AB-IN
Link 文章目录 2940. 花坛的最小改变次数题意思路代码 2940. 花坛的最小改变次数 题意 略 思路 首先需要区间查询gcd#xff0c;想到st表 其次思路#xff0c;固定左端点#xff0c;二分右端点#xff0c;找gcd与区间长度相等的右端点#xff0c;个…Powered by:NEFU AB-IN
Link 文章目录 2940. 花坛的最小改变次数题意思路代码 2940. 花坛的最小改变次数 题意 略 思路 首先需要区间查询gcd想到st表 其次思路固定左端点二分右端点找gcd与区间长度相等的右端点个人是这么理解的 区间长度 mid - i 1gcd区间长度随mid增大而增大gcd随mid增大而减小或不变区间长度开始为1gcd开始大于等于1所以两者如果无限延伸一定有交点可能不止一个所以找到最右边的设为x那么x往左的都是gcd大于等于区间长度的那么把这个区间放进答案数组 在答案数组里按右端点排序如果两个端点可以合并如果某个区间左端点可以小于前哥区间右端点说明可以一起改统计改几次即可 代码
Author: NEFU AB-IN
Date: 2023-06-09 18:00:12
FilePath: \LanQiao\2940\2940.py
LastEditTime: 2023-06-09 20:09:28# import
from sys import setrecursionlimit, stdin, stdout, exit
from collections import Counter, deque
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from bisect import bisect_left, bisect_right
from datetime import datetime, timedelta
from string import ascii_lowercase, ascii_uppercase
from math import log, gcd, sqrt, fabs, ceil, floorclass sa:def __init__(self, x, y):self.x xself.y ydef __lt__(self, a):return self.y a.y# Final
N int(2e5 10)
M 20
INF int(2e9)# Define
setrecursionlimit(INF)
input lambda: stdin.readline().rstrip(\r\n) # Remove when Mutiple data
read lambda: map(int, input().split())
LTN lambda x: ord(x.upper()) - 65 # A - 0
NTL lambda x: ascii_uppercase[x] # 0 - A# —————————————————————Division line ——————————————————————
dp [[0] * M for _ in range(N)]
Log [0] * N
a [0] * Ndef init():for j in range(M):i 1while i (1 j) - 1 n:if j 0:dp[i][j] a[i]else:dp[i][j] gcd(dp[i][j - 1], dp[i (1 (j - 1))][j - 1])i 1for i in range(2, N):Log[i] Log[i // 2] 1def query(l, r):k Log[r - l 1]return gcd(dp[l][k], dp[r - (1 k) 1][k])n, read()
a[1:] read()ans []
init()for i in range(1, n 1):l, r i, nwhile l r:mid l r 1 1if query(i, mid) mid - i 1:l midelse:r mid - 1if query(i, l) l - i 1:ans.append(sa(i, l))cnt 1
if len(ans) 0:print(0)
else:ans.sort()tmp ans[0].yfor i in ans:if i.x tmp:cnt 1tmp i.yprint(cnt)
