简单题目系列之斐波那契数列

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

斐波那契数列众所周知,为了简单起见,我们假设fib(k)代表第k项斐波那契数。
那么:
fib(0)=1
fib(1)=1
fib(2)=2
fib(k) = fib(k-1)+fib(k-2)
已知有以下一个程序
int MAX = 1e18;
int flag[无穷大];
int getAns(int x){
 
    memset(flag,0,sizeof(flag));
    for(int i = 1 ; i<= MAX ; i++){
        p = gcd(fib(x),fib(i))
        flag[p] = 1
    }
 
    int sum = 0;
 
    for(int i = 1 ; i<=无穷大 ;i++){
        sum+=flag[i]
    }
 
    return sum;
}
 
输入x,求getAns(x)的结果
 

Input

 首先输入一个n,代表有n组数据
然后有n行,每行一个x。
(0

Output

 输出有n行,每行对应的为getAns(x)的结果

Sample Input

2
10
8

Sample Output

4
4

Hint

 

Source

zp