问题 H: 三角数
过不了的代码
#include<stdio.h>
int main(){
int t;
scanf("%d",&t);
while(t--){
long long n;
scanf("%lld",&n);
if(n==1){
printf("0\n");
}else if(n==2){
printf("1\n");
}else{
if(n%4==2){
printf("%lld\n",n/2);
}else{
if((n+1)%4==2){
printf("%lld",(n-1)/2);
}else if((n+2)%4==2){
printf("%lld\n",n/2);
}else{
printf("%lld\n",(n+1)/2);
}
}
}
}
return 0;
}
我还找了半天规律，除了前面两行，从第三行开始，连续三个相同的偶数，一个奇数，再是三个连续相同的偶数，再是一个奇数，我发现这个奇数对应的行数刚好是模除
4
4
4 等于
2
2
2 的，我像是发现了新大陆一样，把这个作为一个标准，表示剩余的三个数字，我把数字四个分为一组。还查了一下 long long 可以表示的数据范围，有十九位，交了一发代码，直接 WA 了。测试的数据都和我手写出来的答案一模一样，不知道问题出在哪里。
能过得代码
#include<stdio.h>
int main(){
int t;
scanf("%d",&t);
while(t--){
long long n;
scanf("%lld",&n);
long long st=(1+n-1)*(n-1)/2+1;
long long ed=st+n-1;
if(st%2!=0){
st++;
}
if(ed%2!=0){
ed--;
}
long long ans=(ed-st)/2+1;
printf("%lld\n",ans);
}
return 0;
}
我真的感觉很奇怪呀，上面那个过不了的代码，真感觉没啥问题。能过得代码，思路是，等差数列求和，算出第 n 行第一个数字是啥，等差数列是把每一行得元素个数看成数列得一个元素，一直算到第 n-1 行，然后第 n 行的第一个元素，在这个求和的基础上加一即可。第 n 行的最后一个元素是 st+n-1 ，这个自己找一行模拟一下就好了，比如说
4
,
5
,
6
4 ,5 ,6
4,5,6 ，
n
=
3
n=3
n=3，
6
=
4
+
3
−
1
6=4+3-1
6=4+3−1，感觉这种公式就是这么推出来的。
注意我这里代码把第 n 行第一个偶数元素记为 st ，把这一行最后一个偶数元素记为 ed ，最后面算答案的公式，也是用这种样例模拟的方式找到的公式，我感觉也是找规律，那我最上面找规律为什么过不了呢，非常苦恼。。比如说
4
,
5
,
6
4,5,6
4,5,6，第一个偶数是
4
4
4 ，最后一个偶数元素是
6
6
6,
(
6
−
4
)
/
2
+
1
(6-4)/2+1
(6−4)/2+1 就是答案。多样算几个样例，假设都没问题，基本没啥问题。
( e d − s t ) / 2 + 1 (ed-st)/2+1 (ed−st)/2+1