首页 › 题库 › C/C++编程考级 › C/C++编程三级 › 简答题
简答题 偏难
#7377

数列 用以下方式构造数列: 数列的第一个和第二个数都为1,接下来每个数都等于前面2个数之和。 给出一个正整数a,要求数列中第a个数对1000取模的结果是多少。…

数列

用以下方式构造数列: 数列的第一个和第二个数都为1,接下来每个数都等于前面2个数之和。

给出一个正整数a,要求数列中第a个数对1000取模的结果是多少。

时间限制:1000

内存限制:65536

输入

第1行是测试数据的组数n,后面跟着n行输入。每组测试数据占1行,包括一个正整数a(1 <= a <= 1000000)。

输出

n行,每行输出对应一个输入。输出应是一个正整数,为数列中第a个数对1000取模得到的结果。

样例输入

4
5
2
19
1

样例输出

5
1
181
1
未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">//解法1 #include &lt;iostream&gt;  using namespace std;  int a[1000000]; void sl(){   a[0]=1;a[1]=1;   for(int i=2;i&lt;1000000;i++){     a[i]=a[i-1]+a[i-2];a[i]=a[i]%1000;   } } int main(){     sl();     int b;cin&gt;&gt;b;     for(int i=0;i&lt;b;i++){       int c;cin&gt;&gt;c;       cout&lt;&lt;a[c-1]&lt;&lt;endl;     }     return 0; }</pre><pre class="brush:cpp;toolbar:false">//解法2 斐波那契额数列 #include&lt;bits/stdc++.h&gt; using namespace std; const int N=1e6+5; int a[N]={0,1,1},k=2,n; int fibo(int x){ if(x&lt;=k) return a[x]; for(int i=k+1;i&lt;=x;i++) a[i]=(a[i-1]+a[i-2])%1000; k=x; return a[x]; } int main() {    cin&gt;&gt;n;    for(int i=1,m;i&lt;=n;i++){    cin&gt;&gt;m;    cout&lt;&lt;fibo(m)&lt;&lt;endl;    }    return 0; }</pre>
这道题暂未补解析。