编程介的小学生 2019-08-26 21:59 采纳率: 20.5%
浏览 161

用C语言的程序设计Evil teacher

Problem Description
In the math class, the evil teacher gave you one unprecedented problem!

Here f(n) is the n-th fibonacci number (n >= 0)! Where f(0) = f(1) = 1 and for any n > 1, f(n) = f(n - 1) + f(n - 2). For example, f(2) = 2, f(3) = 3, f(4) = 5 ...

The teacher used to let you calculate f(n) mod p where n <= 10^18 and p <= 10^9, however , as an ACMER, you may just kill it in seconds! The evil teacher is mad about this. Now he let you find the smallest integer m (m > 0) such that for ANY non-negative integer n ,f(n) = f(n + m) (mod p) . For example, if p = 2, then we could find know m = 3 , f(0) = f(3) = 1(mod 2), f(1) = f(4) (mod 2) ....

Now the evil teacher will only give you one integer p( p <= 2* 10^9), will you tell him the smallest m you can find ?

Input
The first line is one integer T indicates the number of the test cases. (T <=20)

Then for every case, only one integer P . (1 <= P <= 2 * 10^9, the max prime factor for P is no larger than 10^6)

Output
Output one line.

First output “Case #idx: ”, here idx is the case number count from 1.Then output the smallest m you can find. You can assume that the m is always smaller than 2^64 .

Sample Input
5
11
19
61
17
67890

Sample Output
Case #1: 10
Case #2: 18
Case #3: 60
Case #4: 36
Case #5: 4440

  • 写回答

2条回答 默认 最新

  • Lighthouses 2019-08-26 23:16
    关注
    评论

报告相同问题?

悬赏问题

  • ¥15 MATLAB怎么通过柱坐标变换画开口是圆形的旋转抛物面?
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名
  • ¥65 汇编语言除法溢出问题
  • ¥15 Visual Studio问题
  • ¥20 求一个html代码,有偿