Wannafly挑战赛9 C

链接：https://www.nowcoder.com/acm/contest/71/C
来源：牛客网

题目描述

小W在计算一个数列{A_n},其中A₁=1,A₂=2,A_n+2=A_n+1+A_n。尽管他计算非常精准，但很快他就弄混了自己的草稿纸，他找出了一些他计算的结果，但他忘记了这些都是数列中的第几项。

输入描述:

每行包括数列中的一项A_k(k<=100000)。

总行数T<=30。

输出描述:

对于每一项A_k，输出一行包括一个正整数k表示输入中数是数列的第几项。

输入例子:

输出例子:

-->

示例1

输入

输出

题解

在$mod({10^9} + 7)$的情况下进行比较即可，据说有冲突，数据有点水过去了，比较稳的方法是找两个不同的$mod$数，如果都一样则一样。

#include <bits/stdc++.h>

using namespace std;

long long mod = 1e9 + 7;

const int maxn = 4e6 + 10;

char s[maxn];

long long a[100010];

int main() {

   a[1] = 1;

   a[2] = 2;

  for(int i = 3; i <= 100000; i ++) {

    a[i] = (a[i - 1] + a[i - 2]) % mod;

  }

  while(~scanf("%s", s)) {

    long long x = 0;

    for(int i = 0; s[i]; i ++) {

      x = x * 10LL % mod;

      x = (x + s[i] - '0') % mod;

    }

    int ans;

    for(int i = 1; i <= 100000; i ++) {

      if(a[i] == x) {

        ans = i;

        break;

      }

    }

    printf("%d\n", ans);

  }

  return 0;

}

巴特西

Wannafly挑战赛9 C - 列一列

题目描述

输入描述:

输出描述:

输入例子:

输出例子:

输入

输出

题解

最新文章

热门文章