ZOJ 3702 Gibonacci number

题目地址:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3702

水题;

预处理下,i和j的范围不大;

G[0]=1,只要求出G[1]就可以解,G[i]=x[i-2]+x[i-1]*G[1] (i>=2)  x[i]是x[1]=x[2]=1的裴波那契数列 (式子好求,列个表写出前几个找规律就好);

AC代码:

#include<iostream>
using namespace std;
long long ltsc[22];
int main()
{
    //预处理裴波那契数列
    ltsc[0]=ltsc[1]=1;
    for(int i=2;i<=20;i++)
    {
        ltsc[i]=ltsc[i-1]+ltsc[i-2];
    }

    int t;
    cin>>t;
    while(t--)
    {
        int i,j;
        long long x,rx;//rx即G[1]
        bool r=true;
        cin>>i>>x>>j;
        if(i==1)rx=x;
        else
        {
            rx=(x-ltsc[i-2]);
            //判断是否存在G[1]
            if(rx%ltsc[i-1]==0)
            {
                rx/=ltsc[i-1];
                r=rx<1?false:true;
            }
            else r=false;
            if(r==false)
            {
                cout<<"-1"<<endl;
                continue;
            }
        }
        cout<<ltsc[j-2]+ltsc[j-1]*rx<<endl;;
    }
}

 

相关日志

  1. 2016.05.09

    FZU 2093 寻找兔子(状压dp)

    题目地址:http://acm.fzu.ed…

  2. 2016.05.09

    FZU 2091 播放器

    题目地址:http://acm.fzu.ed…

  3. 2016.07.13

    安利一波答案 经典算法设计

      (更多…)

  4. 2016.05.12

    ZOJ 3698 Carrot Fantasy(搜索大模拟)

    题目地址:http://acm.zju.ed…

  5. 2016.07.10

    Codeforces Round #361 (Div. 2)B. Mike and Shortcuts

    题意迷之简短。大意就是:一个城市i到另一个城…

  6. 2016.05.04

    FZU 2041 checker(搜索)

    题目链接:http://acm.fzu.ed…

评论

还没有评论。

在此评论中不能使用 HTML 标签。