UVa 11582 (快速幂取模) Colossal Fibonacci Numbers!

时间:2022-09-02 07:48:18

题意:

斐波那契数列f(0) = 0, f(1) = 1, f(n+2) = f(n+1) + f(n) (n ≥ 0)

输入a、b、n,求f(ab)%n

分析:

构造一个新数列F(i) = f(i) % n,则所求为F(ab)

如果新数列中相邻两项重复出现的话,则根据递推关系这个数列是循环的。

相邻两项所有可能组合最多就n2中,所以根据抽屉原理得到这个数列一定是循环的。

求出数列的周期,然后快速幂取模即可。

 #include <cstdio>
#include <iostream>
using namespace std; const int maxn = + ;
typedef unsigned long long ULL;
int f[maxn][maxn * ], period[maxn]; int pow_mod(ULL a, ULL b, int n)
{
if(b == ) return ;
int k = pow_mod(a, b/, n);
k = k * k % n;
if(b % == ) k = k * a % n;
return k;
} int solve(ULL a, ULL b, int n)
{
if(a == || n == ) return ;
int p = pow_mod(a % period[n], b, period[n]);
return f[n][p];
} int main(void)
{
freopen("11582in.txt", "r", stdin);
for(int n = ; n < maxn; ++n)
{
f[n][] = , f[n][] = ;
for(int i = ; ; ++i)
{
f[n][i] = (f[n][i-] + f[n][i-]) % n;
if(f[n][i-] == && f[n][i] == )
{
period[n] = i - ;
break;
}
}
} ULL a, b;
int n, T;
scanf("%d", &T);
while(T--)
{
cin >> a >> b >> n;
printf("%d\n", solve(a, b, n));
} return ;
}

代码君

UVa 11582 (快速幂取模) Colossal Fibonacci Numbers!的更多相关文章

  1. uva 10710 快速幂取模

    //题目大意:输入一个n值问洗牌n-1次后是不是会变成初始状态(Jimmy-number),从案例可看出牌1的位置变化为2^i%n,所以最终判断2^(n-1)=1(mod n)是否成立#include ...

  2. UVA 11609 - Teams 组合、快速幂取模

    看题传送门 题目大意: 有n个人,选一个或者多个人参加比赛,其中一名当队长,如果参赛者相同,队长不同,也算一种方案.求一共有多少种方案. 思路: 排列组合问题. 先选队长有C(n , 1)种 然后从n ...

  3. 【转】C语言快速幂取模算法小结

    (转自:http://www.jb51.net/article/54947.htm) 本文实例汇总了C语言实现的快速幂取模算法,是比较常见的算法.分享给大家供大家参考之用.具体如下: 首先,所谓的快速 ...

  4. HDU 1061 Rightmost Digit --- 快速幂取模

    HDU 1061 题目大意:给定数字n(1<=n<=1,000,000,000),求n^n%10的结果 解题思路:首先n可以很大,直接累积n^n再求模肯定是不可取的, 因为会超出数据范围, ...

  5. POJ3641-Pseudoprime numbers(快速幂取模)

    题目大意 判断一个数是否是伪素数 题解 赤果果的快速幂取模.... 代码: #include<iostream> #include<cmath> using namespace ...

  6. 九度OJ 1085 求root&lpar;N&comma; k&rpar; -- 二分求幂及快速幂取模

    题目地址:http://ac.jobdu.com/problem.php?pid=1085 题目描述: N<k时,root(N,k) = N,否则,root(N,k) = root(N',k). ...

  7. HDU--杭电--4506--小明系列故事——师兄帮帮忙--快速幂取模

    小明系列故事——师兄帮帮忙 Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others) To ...

  8. CodeForces Round &num;191 &lpar;327C&rpar; - Magic Five 等比数列求和的快速幂取模

    很久以前做过此类问题..就因为太久了..这题想了很久想不出..卡在推出等比的求和公式,有除法运算,无法快速幂取模... 看到了 http://blog.csdn.net/yangshuolll/art ...

  9. HDU1013,1163 ,2035九余数定理 快速幂取模

    1.HDU1013求一个positive integer的digital root,即不停的求数位和,直到数位和为一位数即为数根. 一开始,以为integer嘛,指整型就行吧= =(too young ...

随机推荐

  1. 千万级高并发负载均衡软件HAproxy

    1负载均衡产品介绍 基于硬件的负载均衡设备例如F5,Big-IP,基于软件的负载均衡产品HAproxy,LVS,nginx在这些软件产品中,又分为基于操作系统的软负载实现和基于第三方应用的软负载实现. ...

  2. CC1310之使用SMARTRF STUDIO

    SMARTRF STUDIO是TI提供的射频测试软件,在调射频的时候非常非常非常好用,推荐每一个使用TI射频芯片的工程师都要掌握. 1 如何使用? 要使用SMARTRF STUDIO,硬件必须连接仿真 ...

  3. sky简介

    sky简介 sky是一种构建高性能.跨平台手机APP的新的途径.更值得关注的是,sky是一种渲染引擎.脚本引擎.一个框架和一系列的材料设计模式的窗体组件.sky是当前以及未来手机APP的一种优化手段. ...

  4. Mysql常用命令详解

    Mysql安装目录 数据库目录 /var/lib/mysql/ 配置文件 /usr/share/mysql(mysql.server命令及配置文件) 相关命令 /usr/bin(mysqladmin ...

  5. MATLAB 图像分类 Image Category Classification Using Bag of Features

    使用MATLAB实现图像的识别,这是MATLAB官网上面的例子,学习一下. http://cn.mathworks.com/help/vision/examples/image-category-cl ...

  6. 拿什么来拯救你,我的table

    分类: Html/CSS | 转载请注明: 出自 海玉的博客 本文地址: http://www.hicss.net/how-to-save-you-my-table/ table曾经在网页开发中占据着 ...

  7. Cookie的Domain

    每个Cookie都有常用的几个元素:name.value.expires.domain Cookie的Domain 设置cookies时,可以设置cookie的域名参数domain,标识cookie在 ...

  8. Flex移动应用程序开发的技巧和窍门&lpar;三&rpar;

    这是关于 Flex 移动应用程序开发的技巧和窍门系列文章的第三部分内容.第一部分内容主要集中讨论了视图之间以及应用程序执行之间切换时的数据处理.第二部分则主要涵盖了应用程序动作条和标签组件风格化方面的 ...

  9. 给织梦DEDECMS添加栏目图片与英文名显示

    开始做微网站了,不同于传统手机网站,因为微信上的微网站是支持CSS3与HTML5的,好吧,各种要学习的还有很多很多阿~这么多新代码,叹! 本来想转战帝国CMS了,奈何这名字太不对味了,PHPCMS也懒 ...

  10. tcpdump 使用

    例子: 首先切换到root用户 tcpdump -w  aaa.cap   -i eth7   -nn -x  'port  9999'  -c  1 以例子说明参数: -w:输出到文件aaa.cap ...