水题(water) 【斐波那契数列】

题意:

其中,\(f(1)=1,f(2)=1\)。

传送门

分析:

首先先看斐波那契数列的几何意义:

图中各数字为正方形的边长。

可以发现其面积关系刚好满足题目中的等式:

\[\sum_{i=1}^{n}{f(i)}=f(n)\times f(n+1)
\]

因此 \(f(n)\) 实际上就是斐波那契数列,所以当 \(x\) 是斐波那契数时,求 \(m\) 进制下末尾 \(0\) 的个数。否则,求 \(z\) 皇后数(可以预处理出)。

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int maxn=90;
int a[14]={-1, 1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200, 73712};//n皇后前几项
set<ll>st;
ll num[10],e[10];
void init()
{
    ll a=1,b=1,c;
    st.insert(1LL);
    for(int i=1;i<=maxn;i++)
    {
        c=a+b;//cout<<"c="<<c<<endl;
        a=b;
        b=c;
        st.insert(c);
    }
}
ll divide(ll n)
{
    ll cnt=0;
    for(ll i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            num[++cnt]=i;
            e[cnt]=0;
            while(n%i==0)
            {
                e[cnt]++;
                n/=i;
            }
        }
    }
    if(n>1)
    {
        num[++cnt]=n;
        e[cnt]=1;
    }
    return cnt;
}
ll ct(ll x,ll p)
{
    ll cnt=0;
    while(x)
    {
        cnt+=(x/p);
        x/=p;
    }
    return cnt;
}
int main()
{
    ll x,m;
    init();
    scanf("%lld%lld",&x,&m);
    if(st.count(x))//是斐波那契数列
    {
        ll cnt=divide(m);
        ll minn=1e18;//要足够大,小了会WA,注意是求阶乘后面的0的个数
        for(ll i=1;i<=cnt;i++)
        {
            ll t=ct(x,num[i]);
            minn=min(t/e[i],minn);
        }
        printf("%lld\n",minn);
    }
    else
    {
        ll z=(x%min(13*1LL,m))+1;
        printf("%d\n",a[z]);
    }
    return 0;
}

参考博客

原文地址:https://www.cnblogs.com/1024-xzx/p/12706781.html

时间: 04-15

水题(water) 【斐波那契数列】的相关文章

刷题9 斐波那契数列及跳台阶问题

斐波那契数列问题描述:大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项.  n<=39 关于斐波那契数列, 定义是这样的: 因为递归太浪费空间, 所以采用循环: 1 class Solution { 2 public: 3 int Fibonacci(int n) { 4 if(n < 2) 5 return n; 6 int first = 0; 7 int second = 1; 8 int sum = -1; 9 for(int i = 0; i < n

算法题4 斐波那契数列

题目: Fibonacci数列定义如下: 输入n,求f(n) 分析: 在剑指offer上有个O(logn)的算法,本文只做O(n)算法的分析.这其实是一个简单的动态规划问题,问题的结果跟子问题的结果相关,关系式已经给出了,计算中需要保存子问题的结果 跳台阶问题:一个台阶一共有n阶,一次起跳可以跳一阶,也可以跳二阶.问总共有多少中跳法,并对时间复杂度进行分析.该问题也是典型的Fibonacci数列问题,第一次跳1个台阶,接下来有f(n-1)中跳法,第一次跳2个台阶,则接下来有f(n-2)个跳法.

Benelux Algorithm Programming Contest 2014 Final ACM-ICPC Asia Training League 暑假第一阶段第二场 E. Excellent Engineers-单点更新、区间最值-线段树 G. Growling Gears I. Interesting Integers-类似斐波那契数列-递推思维题

先写这几道题,比赛的时候有事就只签了个到. E. Excellent Engineers 传送门: 这个题的意思就是如果一个人的r1,r2,r3中的某一个比已存在的人中的小,就把这个人添加到名单中. 因为是3个变量,所以按其中一个变量进行sort排序,然后,剩下的两个变量,一个当位置pos,一个当值val,通过线段树的单点更新和区间最值操作,就可以把名单确定. 代码: 1 //E-线段树 2 #include<iostream> 3 #include<cstdio> 4 #incl

百度之星题--斐波拉契数列

题目: du熊学斐波那契I Time Limit : 2000/1000ms (C/Other) Memory Limit : 65535/32768K (C/Other) 本次组委会推荐使用C.C++ Problem Description du熊对数学一直都非常感兴趣.最近在学习斐波那契数列的它,向你展示了一个数字串,它称之为"斐波那契"串: 11235813471123581347112358........ 聪明的你当然一眼就看出了这个串是这么构造的:1.先写下两位在0~9范围

“斐波那契数列”衍生题

一.斐波那契数列 斐波那契数列是这样的一组数列:1.1.2.3.5.8.13.21.34.……在数学上,斐波纳契数列以如下被以递推的方法定义:F(1)=1,F(2)=1, F(n)=F(n-1)+F(n-2)(n>=3,n∈N*)即大于2的部分是由前两个相加获得. 若要求第 N 个数的值,我们可以用递归也可以通过迭代的方式求解 1.递归 def fibonacci(n): if n == 1 or n == 2: return 1 return fibonacci(n - 1) + fibona

剑指offer编程题Java实现——面试题9斐波那契数列

题目:写一个函数,输入n,求斐波那契数列的第n项. 1 package Solution; 2 3 /** 4 * 剑指offer面试题9:斐波那契数列 5 * 题目:写一个函数,输入n,求斐波那契数列的第n项. 6 * 0, n=1 7 * 斐波那契数列定义如下:f(n)= 1, n=2 8 * f(n-1)+f(n-2), n>2 9 * @author GL 10 * 11 */ 12 public class No9Fibonacci { 13 14 public static void

算法题---k阶斐波那契数列

#include <iostream> #include <cstdio> #include <stdlib.h> #include <algorithm> using namespace std; int main() { int a[120]; int k, m; while (1) { cout << "输入阶数k和约定的常数max.k和max用空格分开." << endl; cin >> k &

07 斐波那契数列 08 跳台阶 两个题的解答相似

官方正规的数学界的斐波那契数列的定义: 波那契数列(Fibonacci sequence),又称黄金分割数列.因数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:1.1.2.3.5.8.13.21.34.……在数学上,斐波纳契数列以如下被以递推的方法定义:F(1)=1,F(2)=1, F(n)=F(n-1)+F(n-2)(n>=3,n∈N*)在现代物理.准晶体结构.化学等领域,斐波纳契数列都有直接的应用. 是以1

[NOIP1997] P2626 斐波那契数列(升级版)

题目背景 大家都知道,斐波那契数列是满足如下性质的一个数列: • f(1) = 1 • f(2) = 1 • f(n) = f(n-1) + f(n-2) (n ≥ 2 且 n 为整数). 题目描述 请你求出第n个斐波那契数列的数mod(或%)2^31之后的值.并把它分解质因数. 输入输出格式 输入格式: n 输出格式: 把第n个斐波那契数列的数分解质因数. 输入输出样例 输入样例#1: 5 输出样例#1: 5=5 输入样例#2: 6 输出样例#2: 8=2*2*2 说明 n<=48 97年的陈

[codevs]1250斐波那契数列&lt;矩阵dp&gt;

题目描述 Description 定义:f0=f1=1, fn=fn-1+fn-2(n>=2).{fi}称为Fibonacci数列. 输入n,求fn mod q.其中1<=q<=30000. 输入描述 Input Description 第一行一个数T(1<=T<=10000). 以下T行,每行两个数,n,q(n<=109, 1<=q<=30000) 输出描述 Output Description 文件包含T行,每行对应一个答案. 样例输入 Sample I