专栏文章

题解：P14199 [ICPC 2024 Hangzhou R] Make It Divisible

封封禁用户
P14199题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minmtntk
此快照首次捕获于
2025/12/02 04:59
3 个月前
此快照最后确认于
2025/12/02 04:59
3 个月前
查看原文

题目分析

给定长度为nn的序列bb和整数kk，我们需要找到所有满足1≤x≤k1 \leq x \leq k的xx，使得序列bi+xb_i + x成为可除序列。可除序列的定义是：对于任意子区间[l,r][l,r]，存在一个ada_d能整除该区间内所有元素。

解题思路

  1. 可除序列性质：整个序列必须满足最小值能整除所有元素。因此我们需要保证min(b+x)min(b + x)能整除所有bi+xb_i + x。
  2. 数学推导：设m=min(b+x)m = min(b + x)，则必须满足(bi+x)mod  m=0(b_i + x) \mod m = 0对所有ii成立。这等价于(bi−bmin)mod  m=0(b_i - b_{min}) \mod m = 0，其中bminb_{min}是原序列的最小值。
  3. 候选xx计算：有效的xx必须满足x≡(−bmin)mod  gx \equiv (-b_{min}) \mod g，其中gg是序列中所有bi−bminb_i - b_{min}的最大公约数。

算法步骤

  1. 计算序列bb的最小值bminb_{min}和所有bi−bminb_i - b_{min}的GCDgg。
  2. 若g=0g=0（即所有bib_i相等），则所有xx都满足条件。
  3. 否则，计算满足x≡−bminmod  gx \equiv -b_{min} \mod g且1≤x≤k1 \leq x \leq k的xx的个数和总和。

代码实现

PYTHON
import sys 
import math 
 
def solve():
    input = sys.stdin.read().split() 
    ptr = 0 
    T = int(input[ptr])
    ptr += 1 
    for _ in range(T):
        n, k = map(int, input[ptr:ptr+2])
        ptr +=2 
        b = list(map(int, input[ptr:ptr+n]))
        ptr +=n 
        
        b_min = min(b)
        diffs = [num - b_min for num in b]
        g = 0 
        for d in diffs:
            g = math.gcd(g,  d)
        
        if g ==0:
            cnt = k 
            total = k*(k+1)//2 
        else:
            x0 = (-b_min) % g 
            if x0 ==0:
                x0 = g 
            max_x = (k - x0) // g * g + x0 
            if max_x <1:
                cnt =0 
                total=0 
            else:
                cnt = (max_x -x0) // g +1 
                total = cnt * x0 + g * cnt * (cnt -1) //2 
        
        print(cnt, total)
 
solve()
这是一篇Python题解，C++请自己尝试：）

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...