时间限制: 1000 ms 内存限制: 65536 KB
提交数: 46311 通过数: 17428【题目描述】
菲波那契数列是指这样的数列: 数列的第一个和第二个数都为<span id="MathJax-Span-2" class="mrow"><span id="MathJax-Span-3" class="mn">11,接下来每个数都等于前面<span id="MathJax-Span-5" class="mrow"><span id="MathJax-Span-6" class="mn">22个数之和。
给出一个正整数<span id="MathJax-Span-8" class="mrow"><span id="MathJax-Span-9" class="mi">aa,要求菲波那契数列中第<span id="MathJax-Span-11" class="mrow"><span id="MathJax-Span-12" class="mi">aa个数对<span id="MathJax-Span-14" class="mrow"><span id="MathJax-Span-15" class="mn">10001000取模的结果是多少。
【输入】
第<span id="MathJax-Span-17" class="mrow"><span id="MathJax-Span-18" class="mn">11行是测试数据的组数<span id="MathJax-Span-20" class="mrow"><span id="MathJax-Span-21" class="mi">nn,后面跟着<span id="MathJax-Span-23" class="mrow"><span id="MathJax-Span-24" class="mi">nn行输入。每组测试数据占1行,包括一个正整数<span id="MathJax-Span-26" class="mrow"><span id="MathJax-Span-27" class="mi">a<span id="MathJax-Span-28" class="mo">(<span id="MathJax-Span-29" class="mn">1<span id="MathJax-Span-30" class="mo">≤<span id="MathJax-Span-31" class="mi">a<span id="MathJax-Span-32" class="mo">≤<span id="MathJax-Span-33" class="mn">1000000<span id="MathJax-Span-34" class="mo">)a(1≤a≤1000000)。
【输出】
<span id="MathJax-Span-36" class="mrow"><span id="MathJax-Span-37" class="mi">nn行,每行输出对应一个输入。输出应是一个正整数,为菲波那契数列中第<span id="MathJax-Span-39" class="mrow"><span id="MathJax-Span-40" class="mi">aa个数对<span id="MathJax-Span-42" class="mrow"><span id="MathJax-Span-43" class="mn">10001000取模得到的结果。
【输入样例】
4 5 2 19 1
【输出样例】
5 1 181 1
noip更多资料
链接:https://pan.baidu.com/s/1gOOOlCqxtPxgusGKya55Ag?pwd=05d3
#include <iostream> using namespace std; int main() { int n; int a[200]; //输入的第N个数字 int f[1000001]; //将1000000个斐波那契数取1000的模都求出来 f[1]=1; f[2]=1; cin>>n; for(int i=0;i<n;i++) { cin>>a[i]; } for(int i=3;i<1000001;i++) { f[i]=(f[i-1]+f[i-2])%1000; //高精度取模 } for(int i=0;i<n;i++) { cout<<f[a[i]]<<endl; //将输入的数字a[i]当成脚标用于f[]中,求出输入数字的斐波那契数取模的结果 } return 0; }
标签:aa,数列,1188,int,奥赛,菲波,nn,那契 From: https://www.cnblogs.com/sd129/p/16659950.html