P11129 【MX-X5-T1】「GFOI Round 1」Inverted World

题目背景

原题链接：https://oier.team/problems/X5B。

---

Inverted World - ARForest

题目描述

给定一个长度为 $n$ 的正整数序列 $(a_1,\dots ,a_n)$，保证该序列是等差数列。
（如果你不知道等差数列的定义，请参阅题目末尾处的提示。）

请求出该序列中满足如下条件的连续非空子串 $(a_l,\dots ,a_r)$（$1\le l\le r\le n$）的数量：

• 该子串中的元素的平均值是整数。
  （即 $(a_l+\cdots +a_r)÷(r-l+1)$ 是整数。）

该序列可能很长，即 $n$ 可能很大，故不会给出该序列的每一项，而是只给出长度 $n$、首项 $k$ 和公差 $d$。保证 $\mathbf{k},\mathbf{d}$ 都是正整数。

输入格式

本题有多组测试数据。

第一行输入一个正整数 $T$，表示测试数据组数。

对于每组测试数据：

第一行包含三个正整数 $n,k,d$。

输出格式

对于每组数据，输出一行一个非负整数，表示平均数为整数的子段个数。

输入输出样例 #1

输入 #1

3
2 1 2
3 2 5
11451 41 91981

输出 #1

3
4
32787076

说明/提示

【样例解释】

在第一组数据中，$a=[1,3]$。共有 $3$ 个连续非空子串满足要求：

• $[1]$，其平均值为 $1$；
• $[3]$，其平均值为 $3$；
• $[1,3]$，其平均值为 $2$。

在第二组数据中，$a=[2,7,12]$。共有 $4$ 个连续非空子串满足要求：

• $[2]$，其平均值为 $2$；
• $[7]$，其平均值为 $7$；
• $[12]$，其平均值为 $12$；
• $[2,7,12]$，其平均值为 $7$。

【数据范围】

测试点编号	$n\le$	$k\le$	$d\le$	分值
$1$	$10$	$10$	$10$	$28$
$2$	$10^9$	$10^9$	$1$	$35$
$3$	$10^9$	$10^9$	$10^9$	$37$

对于所有数据，满足 $1\le T\le 10^3$，$1\le n,k,d\le 10^9$。

【提示】

长度为 $n$、首项为 $k$、公差为 $d$ 的等差数列定义为 $a_1=k$ 且 $a_i=a_{i-1}+d$（对每个 $2\le i\le n$）。

C++实现

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

int main(){
int t;
cin>>t;

while(t--){
	long long n,k,d,ans=n;
	cin>>n>>k>>d;
	
	if(d%2==0){
		ans=n*(n-1)/2;
		cout<<ans+n<<"\n";
	}
	else{
		if(n%2==0){
			ans=(2+n)*(n-4)/4+2; 
		}
		else{
			ans=(n/2)*(n/2);
		}
		cout<<ans+n<<"\n";
	}
}
return 0;

}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容