HDOJ1021题 Fibonacci Again 应用求模公式

Stella981
• 阅读 647

Problem Description
There are another kind of Fibonacci numbers: F(0) = 7, F(1) = 11, F(n) = F(n-1) + F(n-2) (n>=2).

Input
Input consists of a sequence of lines, each containing an integer n. (n < 1,000,000).

Output
Print the word “yes” if 3 divide evenly into F(n).

Print the word “no” if not.

Sample Input
0
1
2
3
4
5

Sample Output
no
no
yes
no
no
no

应用求模公式
(1) (a + b) % p = (a % p + b % p) % p
(2) (a - b) % p = (a % p - b % p) % p
(3) (a * b) % p = (a % p * b % p) % p
(4) a ^ b % p = ((a % p)^b) % p
如果不用的话会溢出。
代码:

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include<string.h>
using namespace std;

int main()
{
    int a[1000001],i,j,s;
    a[0]=7;a[1]=11;
    for(i=2;i<1000001;i++)
    {
        a[i]=(a[i-1]%3+a[i-2]%3)%3;//只写最后那个%3也可以
    }
    while(~scanf("%d",&s))
    {
        if(a[s]%3==0)
            printf("yes\n");
        else
            printf("no\n");
    }
    return 0;
}

本文同步分享在 博客“谙忆”(CSDN)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

点赞
收藏
评论区
推荐文章
blmius blmius
3年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
待兔 待兔
4个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Stella981 Stella981
3年前
Hacker News 简讯 2021
!(https://oscimg.oschina.net/oscnet/up3b137e2e6620f7a63f11a96485b1fb3b.png)最后更新时间:2021011823:00
Wesley13 Wesley13
3年前
PHP创建多级树型结构
<!lang:php<?php$areaarray(array('id'1,'pid'0,'name''中国'),array('id'5,'pid'0,'name''美国'),array('id'2,'pid'1,'name''吉林'),array('id'4,'pid'2,'n
Stella981 Stella981
3年前
Hacker News 简讯 2020
!(https://oscimg.oschina.net/oscnet/up3b137e2e6620f7a63f11a96485b1fb3b.png)最后更新时间:2020082623:00
Stella981 Stella981
3年前
HDU1005 Number Sequence
HDU1005NumberSequence(https://www.oschina.net/action/GoToLink?urlhttp%3A%2F%2Facm.hdu.edu.cn%2Fshowproblem.php%3Fpid%3D1005)对于公式f\n\A\f\n1\B\f\n2\,因为对于f\n1\
Wesley13 Wesley13
3年前
ES6 新增的数组的方法
给定一个数组letlist\//wu:武力zhi:智力{id:1,name:'张飞',wu:97,zhi:10},{id:2,name:'诸葛亮',wu:55,zhi:99},{id:3,name:'赵云',wu:97,zhi:66},{id:4,na
Stella981 Stella981
3年前
Forrester机器学习报告发布,腾讯云跃居第一阵营
  !(https://nimg.ws.126.net/?urlhttp%3A%2F%2Fdingyue.ws.126.net%2F2020%2F1016%2Fecdc1f59j00qi98j7000od200u000fpg00it009u.jpg&thumbnail650x2147483647&quality80&typejpg)  A
Wesley13 Wesley13
3年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
Python进阶者 Python进阶者
10个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这