nyoj 102 次方求摸 快速幂
2024-10-18 07:21:57
次方求模
时间限制：1000 ms | 内存限制：65535 KB
难度：3
- 描述
-
求a的b次方对c取余的值
- 输入
- 第一行输入一个整数n表示测试数据的组数（n<100）
每组测试只有一行，其中有三个正整数a,b,c(1=<a,b,c<=1000000000)
- 输出
- 输出a的b次方对c取余之后的结果
- 样例输入
-
3
2 3 5
3 100 10
11 12345 12345 - 样例输出
-
3
1
10481
把指数反复二分。最后再合并，很裸的快速幂，注意题目中没有0次方的情况，否则递归的if要改成if(b == 0) return 1;
#include<stdio.h>
int f(int a, int b , int c)
{
if(b == 1)
return a % c;
long long num;
num = f(a , b/2 , c);
if(b % 2 == 1)
num = ((num * num % c) * a) % c;
else
num = (num * num) % c;
return num;
}
int main()
{
int num;
int a , b , c; scanf("%d" , &num);
while(num--)
{
scanf("%d %d %d" , &a , &b , &c);
if(a == c || c == 1)
printf("0\n");
else
printf("%d\n" , f(a , b , c));
}
return 0;
}
最新文章
- Android使用SAX解析XML(3)
- Yii笔记---redirect重定向
- 《嵌入式Linux基础教程》补充阅读建议电子数目下载
- hdu 3359 Kind of a Blur (高斯消元 浮点型)
- HTTP请求中浏览器缓存
- linux多线程驱动中调用udelay（）对整个系统造成的影响（by liukun321咕唧咕唧）
- 有关UITableViewCell的侧滑删除以及使用相关大神框架MGSwipeTableCell遇到的小问题
- LB集群
- c/c++中宏定义##连接符 和#符的使用
- Spring Boot 系列教程10-freemarker导出word下载
- 使用git bash提交代码到github托管
- hibernate解读之session--基于最新稳定版5.2.12
- Python科学计算基础包-Numpy
- python中类似三元表达式的写法
- （ZT）算法杂货铺——分类算法之朴素贝叶斯分类(Naive Bayesian classification)
- 12.1-uC/OS-III调度的内部实现
- xml配置文件中常见的命名空间解释
- js中var的有或无--重复声明和以后的声明
- 用图来教你怎样用Photoshop蓝底转换红底
- SVG 使用marker画箭头（一）