东大OJ-1391-Big big Power
2024-09-24 14:24:02
题目描述
Calculate the power num a^(b^c) mod 1e9+7
输入
Multiple test cases,each case has three integers a,b and c . a,b,c is less than 1e9;
输出
Output the answer in each line
样例输入
2 3 2
样例输出
512
需要用到费马小定理.如果p是质数,并且a不等于1且a不等于p,那么 a^(p-1)%p====1.
所以,a^1000000006 % 1000000007=1.
a^b^c%1000000007=a^(b^c % 1000000006) % 1000000007.
这是第一关.用费马小定理将问题化简一下.
第二关是快速幂,用递归实现特别清晰.
九指神丐洪七公曾经告诉郭靖:遇到敌人不要把注意力放在敌人出什么招数上,你只需要把这降龙十八掌一遍一遍的使将出来,必可立于不败之地.
管他是否多余,多用long long int.各种取余.
为了安全,可以适当的冗余.尤其是现在的大程序.
#include<iostream> using namespace std; long long int go(long long int a, long long int b, long long int c){ if (b == 0)return 1; long long int t = go(a, b / 2, c); long long int p = (t*t) % c; if (b % 2 == 0)return p; return (p*a) % c; } int main(){ //freopen("in.txt", "r", stdin); long long int a, b, c; while (cin >> a >> b >> c) cout << go(a, go(b, c, 1000000006), 1000000007)<<endl; return 0; }
最新文章
- CORS简介
- ElasticSearch性能优化官方建议
- java之yield(),sleep(),wait()区别详解
- C#一维数组
- Maven实战(四)生命周期
- XML xsd
- 第二课 android项目结构
- asp.net Calendar 日历控件用法
- 《Genesis-3D开源游戏引擎完整实例教程-2D射击游戏篇08:弹幕系统》本系列完结
- onS 记录
- Java简单实现UDP和TCP
- 算法-java代码实现选择排序
- springboot情操陶冶-web配置(九)
- toLatin1 qt
- JDBC四种驱动程序
- System.Collections 学习
- JavaScript 删除数组中的对象
- 从数据库中取 datetime类型,界面展示 yyyy-MM-dd
- poj3254 Corn Fields
- IntelliJ IDEA 学习(三):IntelliJ IDEA 快捷键、配置优化