[BZOJ 3713]Iloczyn

danihao123 posted @ 2016年7月16日 20:24 in 题解 with tags bzoj PA 数学 , 356 阅读
转载请注明出处:http://danihao123.is-programmer.com/

这题应该注意到,斐波纳契函数增长速度很快,[tex]10^9[/tex]以下的斐波纳契函数值很少,所以可以打表。这样,问题就迎刃而解了。

代码:

/**************************************************************
    Problem: 3713
    User: danihao123
    Language: C++
    Result: Accepted
    Time:20 ms
    Memory:828 kb
****************************************************************/
 
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int fib[46]={0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733,1134903170};
bool check(int n){
    int m=sqrt(0.5+n);
    if(binary_search(fib,fib+46,n))
        return true;
    register int i;
    for(i=2;i<=m;i++){
        if(!(n%i) && binary_search(fib,fib+46,i)){
            if(binary_search(fib,fib+46,n/i))
                return true;
        }
    }
    return false;
}
int main(){
    int T,n;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        if(check(n))
            puts("TAK");
        else
            puts("NIE");
    }
    return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter