[BZOJ 3713]Iloczyn

danihao123 posted @ 2016年7月16日 20:24 in 题解 with tags bzoj PA 数学 , 759 阅读
转载请注明出处: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;
}
blogss.in 说:
Jul 01, 2023 06:05:24 PM

who have come together for dedicated news coverage of latest happenings around the country.Our team comprises of professional writers & citizen journalists with diverse range of interest in Journalism who are passionate about publishing the Education Updates with transparency in general public interest is a initiative of professional writers blogss.in who have come together for dedicated news coverage of latest happenings around the country (India). Our team comprises of professional writers & citizen journalists.

mon activité android 说:
Jul 13, 2023 12:32:28 AM

Mon activité est le portail principal où vous pouvez voir vos activités Google, y compris les recherches, les sites que vous avez visités et les films que vous avez visionnés. Il est important de noter que lors de l’utilisation des sites, applications et services Google. mon activité android Ils sont conservés indéfiniment dans votre compte Google. Vous pouvez afficher ou supprimer l’historique Google de mon activité en vous rendant dans Mon activité.


登录 *


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