做题网站推荐: OpenJudge VIJOS UOJ CF JOYOI CODEVS 洛谷 RQNOJ BZOJ POJ HDU 牛客网

本站题目推荐: 高精度 模拟 排序 递推 贪心 递归 搜索 动态规划 数学 图论 数据结构 实名认证 卡评测举报

输入输出 变量类型 顺序结构 选择结构 循环结构 一维数组 NOIP 资源下载


问题 2924. -- 「一本通 6.5 例 4」佳佳的 Fibonacci

2924: 「一本通 6.5 例 4」佳佳的 Fibonacci

时间限制: 1 Sec  内存限制: 512 MB
提交: 1  解决: 0
[上一题][提交][讨论版][状态][下一题]

题目描述

佳佳对数学,尤其对数列十分感兴趣。在研究完 Fibonacci 数列后,他创造出许多稀奇古怪的数列。例如用 S(n)S(n)S(n) 表示 Fibonacci 前 nnn 项和 modm 的值,即 S(n)=(F1+F2+...+Fn)modm,其中 F1=F2=1,Fi=Fi−1+Fi−2F_1=F_2=1, F_i=F_{i-1}+F_{i-2}F1=F2=1,Fi=Fi1+Fi2。可这对佳佳来说还是小菜一碟。

终于,她找到了一个自己解决不了的问题。用 T(n)=(F1+2F2+3F3+...+nFn)modm 表示 Fibonacci 数列前 nnn 项变形后的和 modm 的值。

现在佳佳告诉你了一个 nnnmmm,请求出 T(n)T(n)T(n) 的值。

输入

输入数据包括一行,两个用空格隔开的整数 n,mn,mn,m

输出

仅一行,T(n)T(n)T(n) 的值。

提示

样例输入

5 5

样例输出

1

样例解释

T(5)=(1+2×1+3×2+4×3+5×5)mod5=1

对于 30%30\%30% 的数据,1≤n≤10001le n le 10001n1000

对于 60%60\%60% 的数据,1≤m≤10001le m le 10001m1000

对于 100%100\%100% 的数据,1≤n,m≤231−11le n,m le 2^{31}-11n,m2311

标签

[上一题][提交][讨论版][状态][下一题]