洛谷 P1795 无穷的序列 题解

题目传送门

题目大意：给定整数 \(a\)，判断 \(a\) 是否属于数列 \(1,2,4,7,11\cdots\)。多测。

1. 暴力枚举（90pts）

不难发现，该数列除第一项外第 \(n\) 项比第 \(n-1\) 项多 \(n-1\)。故暴力枚举 \(n\)，计算数列的每一项，判断是否与 \(a\) 相等，大于 \(a\) 就 break。

多测加记忆化，用 mx 表示已处理的最大项数，在 mx 内的项直接读记忆。

#11 TLE。

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

bool f;
ll q,a,s,mx=-1;
map<ll,bool> b;
int main(void) {
  scanf("%lld",&q);
  while (q--) {
    scanf("%lld",&a);
    if (a<=mx) putchar(b[a]+'0');
    else {
      mx=a, s=1, f=1;
      for (ll n=1; s<=a; n++) {
        if (s==a) {
          f=0, b[a]=1;
          putchar('1');
          break;
        }
        s+=n;
        b[s]=1;
      }
      if (f) putchar('0');
    }
    putchar('\n');
  }
  return 0;
}

2. 数学法（AC）

该数列通项公式为 \(a_n=\dfrac{n(n-1)}{2}+1\)。

则只需解方程 \(\dfrac{n(n-1)}{2}+1=a\) 即 \(n^2-n-2a+2=0\)，判断 \(n\) 是否为正整数即可。

\(n=\dfrac{1+\sqrt{8a-7}}{2}\)

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

ll q,a;
int main(void) {
  scanf("%lld",&q);
  while (q--) {
    scanf("%lld",&a);
    if (a==1 || a==2) putchar('1'); // 特判 省时间
    else {
      a=(a<<3)-7;
      double n=(1+sqrt(a))/2;
      if (n==floor(n)) putchar('1'); // 判断是否为整数
      else putchar('0');
    }
    putchar('\n');
  }
  return 0;
}