P4994 终于结束的起点————C

2024-01-08 04:28
文章标签 起点 终于 结束 p4994

本文主要是介绍P4994 终于结束的起点————C,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

  • 终于结束的起点
    • 题目背景
    • 题目描述
    • 输入格式
    • 输出格式
    • 样例 #1
      • 样例输入 #1
      • 样例输出 #1
    • 样例 #2
      • 样例输入 #2
      • 样例输出 #2
    • 提示
        • 样例 1 解释
        • 数据范围
        • 提示
  • 解题思路
  • Code
  • 运行结果

终于结束的起点

题目背景

终于结束的起点
终于写下句点
终于我们告别
终于我们又回到原点
……

一个个 OIer 的竞赛生涯总是从一场 NOIp 开始,大多也在一场 NOIp 中结束,好似一次次轮回在不断上演。
如果这次 NOIp 是你的起点,那么祝你的 OI 生涯如同夏花般绚烂。
如果这次 NOIp 是你的终点,那么祝你的 OI 回忆宛若繁星般璀璨。
也许这是你最后一次在洛谷上打比赛,也许不是。
不过,无论如何,祝你在一周后的比赛里,好运。

当然,这道题也和轮回有关系。

题目描述

广为人知的斐波拉契数列 f i b ( n ) \mathrm{fib}(n) fib(n) 是这么计算的

f i b ( n ) = { 0 , n = 0 1 , n = 1 f i b ( n − 1 ) + f i b ( n − 2 ) , n > 1 \mathrm{fib}(n)=\begin{cases} 0,& n=0 \\ 1,& n=1 \\ \mathrm{fib}(n-1) + \mathrm{fib}(n-2),& n>1 \end{cases} fib(n)= 0,1,fib(n1)+fib(n2),n=0n=1n>1

也就是 0 , 1 , 1 , 2 , 3 , 5 , 8 , 13 ⋯ 0, 1, 1, 2, 3, 5, 8, 13 \cdots 0,1,1,2,3,5,8,13,每一项都是前两项之和。

小 F 发现,如果把斐波拉契数列的每一项对任意大于 1 1 1 的正整数 M M M 取模的时候,数列都会产生循环。

当然,小 F 很快就明白了,因为 ( f i b ( n − 1 ) m o d M \mathrm{fib}(n - 1) \bmod M fib(n1)modM) 和 ( f i b ( n − 2 ) m o d M ) \mathrm{fib}(n - 2) \bmod M) fib(n2)modM) 最多只有 M 2 M ^ 2 M2 种取值,所以在 M 2 M ^ 2 M2 次计算后一定出现过循环。

甚至更一般地,我们可以证明,无论取什么模数 M M M,最终模 M M M 下的斐波拉契数列都会是 0 , 1 , ⋯ , 0 , 1 , ⋯ 0, 1, \cdots, 0, 1, \cdots 0,1,,0,1,

现在,给你一个模数 M M M,请你求出最小的 n > 0 n > 0 n>0,使得 f i b ( n ) m o d M = 0 , f i b ( n + 1 ) m o d M = 1 \mathrm{fib}(n) \bmod M = 0, \mathrm{fib}(n + 1) \bmod M = 1 fib(n)modM=0,fib(n+1)modM=1

输入格式

输入一行一个正整数 M M M

输出格式

输出一行一个正整数 n n n

样例 #1

样例输入 #1

2

样例输出 #1

3

样例 #2

样例输入 #2

6

样例输出 #2

24

提示

样例 1 解释

斐波拉契数列为 0 , 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , ⋯ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, \cdots 0,1,1,2,3,5,8,13,21,34,,在对 2 2 2 取模后结果为 0 , 1 , 1 , 0 , 1 , 1 , 0 , 1 , 1 , 0 , ⋯ 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, \cdots 0,1,1,0,1,1,0,1,1,0,

我们可以发现,当 n = 3 n = 3 n=3 时, f ( n ) m o d 2 = 0 , f ( n + 1 ) m o d 2 = 1 f(n) \bmod 2= 0, f(n + 1) \bmod 2 = 1 f(n)mod2=0,f(n+1)mod2=1,也就是我们要求的 n n n 的最小值。

数据范围

对于 30 % 30\% 30% 的数据, M ≤ 18 M \leq 18 M18

对于 70 % 70\% 70% 的数据, M ≤ 2018 M \leq 2018 M2018

对于 100 % 100\% 100% 的数据, 2 ≤ M ≤ 706150 = 0xAC666 2 \leq M \leq 706150=\verb!0xAC666! 2M706150=0xAC666

提示

如果你还不知道什么是取模 ( m o d ) (\bmod) (mod),那我也很乐意告诉你,模运算是求整数除法得到的余数,也就是竖式除法最终「除不尽」的部分,也即
a m o d M = k ⟺ a = b M + k ( M > 0 , 0 ≤ k < M ) a \bmod M =k \iff a = bM + k\ (M > 0, 0 \leq k < M) amodM=ka=bM+k (M>0,0k<M)
其中 a , b , k a, b, k a,b,k 都是非负整数。

如果你使用 C / C++,你可以使用 % 来进行模运算。

如果你使用 Pascal,你可以使用 mod 来进行模运算。

解题思路

  • 首先写出斐波那契数列,然后根据题意进行判断,最终得出结果。

Code

#include<iostream>
#include<vector>using namespace std;int n;
vector<int> nums(5);int main() {cin >> n;nums[0] = 0;nums[1] = 1;for (int i = 1;; i++) {int tmp = nums[0];nums[0] = nums[1];nums[1] = (tmp + nums[1]) % n;if (nums[0] % n == 0 && nums[1] % n == 1) {cout << i;break;}}return 0;
}

运行结果

这篇关于P4994 终于结束的起点————C的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/582305

相关文章

起点中文网防止网页调试的代码展示

起点中文网对爬虫非常敏感。如图,想在页面启用调试后会显示“已在调试程序中暂停”。 选择停用断点并继续运行后会造成cpu占用率升高电脑卡顿。 经简单分析网站使用了js代码用于防止调试并在强制继续运行后造成电脑卡顿,代码如下: function A(A, B) {if (null != B && "undefined" != typeof Symbol && B[Symbol.hasInstan

如何保证android程序进程不到万不得已的情况下,不会被结束

最近,做一个调用系统自带相机的那么一个功能,遇到的坑,在此记录一下。 设备:红米note4 问题起因 因为自定义的相机,很难满足客户的所有需要,比如:自拍杆的支持,优化方面等等。这些方面自定义的相机都不比系统自带的好,因为有些系统都是商家定制的,难免会出现一个奇葩的问题。比如:你在这款手机上运行,无任何问题,然而你换一款手机后,问题就出现了。 比如:小米的红米系列,你启用系统自带拍照功能后

终于解决了excel操作及cspreadsheet.h问题

困扰多日的excel操作问题终于解决:利用cspreadsheet.h!在vs2005下,不能直接应用cspreadsheet.h,所以必须解决些问题先。 首先, 出现暴多错误。解决UNICODE问题,全部添加L。 [1] +++++++++++++++++++ 其次, 出现问题: error   C2664:   &apos;SQLGetInstalledDriversW &apos;

淘应用宣告结束 U站后来居上

目前,输入淘宝买家应用中心(yingyong.taobao.com)原有域名后将直接跳转至淘宝U站,而淘江湖则合并至“我的淘宝”。 据了解,所谓appkey是供淘宝客调用淘宝商家的数据,优站导航能够很方便的使淘宝客在自己的网站里显示淘宝卖家的商品详情。此次调整意味着,淘宝客所调用的数据接口将不再支持淘宝U站中心和淘江湖。 淘宝方面解释,此次调整主要源于淘宝优站中心(含原淘宝U站业务)已于201

adb shell 执行后台程序后断开adb后台进程被结束的解决办法

环境:Android 版本 Android8 通常让程序后台执行就是在命令 最后加上 &即可,但是在Android 8上实验发现,程序的确后台了,但是拔掉USB线再连接上发现进程已结束。不确定Android早期版本是否存在此问题。 参考网上一些Linux方法,如加nohup 仍然无效,还是会结束。看来Android adb shell 与 Linux shell 还是有一定区别。 后来在网上

c语言getchar()接收字符函数如何结束

int main(int argc, char* argv[]) {  double nc;  for(nc=0;getchar()!=EOF;nc++) {     putchar(c); }     printf("%f",nc);  return 0; } 当我们输入字符的时候,注意到,这个并没有按程序的逻辑输入一个就立刻打印出来,因为存在缓存问题,只有按enter键 才会将

Spark 全套知识体系,终于搞到了!

福利手慢无 ☆☞ 廖雪峰的大数据开发必备教程-Spark视频资料终于免费啦!限额领取~ 2019年已过去3/4,年初许下的愿实现了吗?可爱的程序员们都有哪些愿望呢? 找个女朋友。升级电脑、键盘、鼠标等。来一次说走就走的旅行。升职&加薪。…… 说起“升职&加薪”,一向“多金”的程序员们,今年的职场晋升似乎并非那么顺畅。说是大环境所致,这也没错。 但有一部

Flink实例(114):自定义时间和窗口的操作符(十三)自定义窗口分配器之设定窗口开始与结束时刻

1. 自定义窗口分配器(flink1.11.2) package com.atguigu.exercise.ETL.caiutilimport java.text.SimpleDateFormatimport java.utilimport java.util.{Collections, Date}import org.apache.flink.api.common.Executio

QT5.15.2使用QXlsx读取Excel文件后退出程序时程序异常结束

QT5.15.2使用QXlsx读取Excel文件后退出程序时程序异常结束 这是一个困扰了我很久的问题,今天终于解决啦。 异常场景 我的情况是只要用了QXlsx去操作Excel文件后,在关闭程序时无法正常退出程序,会卡住,过一会后在QT的IDE上显示程序异常结束。 解决方法 主要原因在于QXlsx源码的xlsxcellreference.cpp中, 我们只需要找到void CellRefe

终于知道如何简化时间序列的特征工程了!

在处理时间序列数据时,时间特征往往是最基础且独特的要素,我们的目标通常是预测某种未来的响应或结果。 不过在很多情况下,除了时间特征之外,我们还能获取到一系列其他相关的特征或变量。 时间序列数据中的特征工程涉及从原始时间序列数据中创建信息丰富的特征,以提升机器学习模型的性能。 以下是时间序列数据中一些常见的特征类型: 日期时间相关特征: 这些特征是从日期时间列中提取的,如月份、日期、星期