P8177 「EZEC-11」等差数列

题目传送门

思路：

用二进制转换数列的公差，设末尾有 $k$ 个零（也就是可以被 $2$ 整除几次）,那么公式就为：

$$ans=(2^k-1)\times(n-1)$$

那我们是怎么得到的呢？

证明：

首先先搞出来一组简单的样例：

$2\quad2\quad8$

开始模拟：

首先列出数列所有的数：

$2\quad10$

在中间插入第一个数: $\dfrac{(2+10)}{2}$

变成：

$2\quad6\quad10$

那么 $ans=1$

---

然后接着插入。

就变成了：

$2\quad4\quad6\quad8\quad10$

此时 $ans=3$

---

接着插入，就变成了：

$2\quad3\quad4\quad5\quad6\quad7\quad8\quad9\quad10$

此时 $ans=7$

因为不能再插了，所以结束程序。

---

如果我们把加入的数看成一个类似树状的结构，那么就是(因为不怎么用画图，画的很惨烈）：

那么你会发现：这不就是满二叉树吗？

设这棵树的深度为 $k$ ，则插入的数就为这棵树的节点数：

$$2^k-1$$

如果当前数列初始数有 $n$ 个呢？

那肯定每一个空格都可以填，也就是有 $n-1$ 个空格。

所以公式就是：

$$(2^k-1)\times(n-1)$$

AC代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int quick_pow(int x){//快速幂优化
	int ans=1,a=2;
	while(x){
		if(x%2)ans*=a;
		a*=a;
		x/=2;
	}
	return ans;
}
signed main(){
	int t;
	cin>>t;
	while(t--){
		int n,a,d;
		cin>>n>>a>>d;//循环输入
		int cnt=0;
		while(d%2==0){//求能被2整除几次
			cnt++;
			d/=2;
		} 
		int aans=(quick_pow(cnt)-1)*(n-1);//带入公式
		cout<<aans<<endl;//输出
	}
	return 0;//结束程序
}
		 

这道题挺考思维能力的。

果然是一道普及-的题啊。