小欧的等差数列

[题目链接](https://www.nowcoder.com/practice/7c29bf99543040efa8e493b803050bdc)

思路

给定等差数列 $a, a+d, a+2d, \ldots, a+(n-1)d$ ，每次可以选两个数 $x, y$ ，若 $(x+y)/2$ 是整数，就把它加入集合。求集合最终最大元素个数。

核心观察：最小可达步长

不妨将所有元素平移，令首项为 $0$ ，集合变为 $\{0, d, 2d, \ldots, (n-1)d\}$ （平移不影响中点运算）。

取两个元素 $id$ 和 $jd$ ，中点为 $(i+j)d/2$ 。要求它是整数，即 $(i+j)d$ 是偶数。

若 $d$ 是奇数，则需要 $i+j$ 为偶数（同奇偶），中点 $= \frac{i+j}{2} \cdot d$ ，仍是 $d$ 的整数倍，不产生新元素。
若 $d$ 是偶数，则 $(i+j)d$ 恒为偶数，中点 $= (i+j) \cdot \frac{d}{2}$ ，步长缩小为 $d/2$ 。

反复对新集合继续操作，每次 $d$ 含因子 $2$ 时步长就可以再减半。设 $d = 2^v \cdot q$ （ $q$ 为奇数， $v$ 为 $d$ 的 $2$ -adic 赋值），则最终步长缩至 $q$ （奇数后无法再减半）。

推导答案

最终集合覆盖区间 $[0, (n-1)d]$ 中所有 $q$ 的整数倍：

$ $\text{答案} = \frac{(n-1)d}{q} + 1 = (n-1) \cdot 2^v + 1$ $

特殊情况

$n \leq 1$ ：集合最多 $1$ 个元素。
$d = 0$ ：所有元素相同，答案 $= 1$ 。

样例验证

$n=5, a=1, d=2$ 。 $d = 2^1 \cdot 1$ ， $v = 1$ 。答案 $= 4 \times 2 + 1 = 9$ 。

原集合 $\{1, 3, 5, 7, 9\}$ ，取相邻元素中点得 $2, 4, 6, 8$ ，最终集合 $\{1, 2, \ldots, 9\}$ ，共 $9$ 个，正确。

代码

C++
Java
Python3
JavaScript

#include <bits/stdc++.h>
using namespace std;
int main(){
    long long n, a, d;
    cin >> n >> a >> d;
    if(n <= 1 || d == 0){
        cout << 1 << endl;
        return 0;
    }
    if(d < 0) d = -d;
    long long v = 0;
    long long dd = d;
    while(dd % 2 == 0){
        dd /= 2;
        v++;
    }
    cout << (n - 1) * (1LL << v) + 1 << endl;
    return 0;
}

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong(), a = sc.nextLong(), d = sc.nextLong();
        if (n <= 1 || d == 0) {
            System.out.println(1);
            return;
        }
        if (d < 0) d = -d;
        long v = 0, dd = d;
        while (dd % 2 == 0) { dd /= 2; v++; }
        System.out.println((n - 1) * (1L << v) + 1);
    }
}

n, a, d = map(int, input().split())
if n <= 1 or d == 0:
    print(1)
else:
    if d < 0:
        d = -d
    v = 0
    dd = d
    while dd % 2 == 0:
        dd //= 2
        v += 1
    print((n - 1) * (1 << v) + 1)

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
rl.on('line', (line) => {
    let [n, a, d] = line.trim().split(' ').map(Number);
    if (n <= 1 || d === 0) { console.log(1); return; }
    if (d < 0) d = -d;
    let v = 0, dd = d;
    while (dd % 2 === 0) { dd = Math.floor(dd / 2); v++; }
    console.log((n - 1) * Math.pow(2, v) + 1);
});

复杂度

时间复杂度： $O(\log d)$ ，只需计算 $d$ 中因子 $2$ 的个数。
空间复杂度： $O(1)$ 。