首页 > 其他分享 >AcWing 875. 快速幂

AcWing 875. 快速幂

时间:2023-08-27 18:31:31浏览次数:55  
标签:d% int res LL 875 long fast 快速 AcWing

JWvFczgRNg.jpg

题目

给定 $n$ 组 $a_i,b_i,p_i$,对于每组数据,求出 ${a_i}^{b_i}mod{p_i}$ 的值。

输入格式 第一行包含整数 $n$。

接下来 $n$ 行,每行包含三个整数 $a_i,b_i,p_i$。

输出格式 对于每组数据,输出一个结果,表示 ${a_i}^{b_i}mod{p_i}$ 的值。

每个结果占一行。

数据范围 $1≤n≤100000,1≤a_i,b_i,p_i≤2×10^9$ 输入样例:

2
3 2 5
4 3 9

输出样例:

4
1

思路

主要思路是将 $b$ 转换成二进制,将二进制中位为 $1$ 的初始化,最终结果由预处理的数值拼凑而成。

代码

#include <iostream>

using namespace std;

typedef long long LL;

// 快速幂代码
int fast_power(int a, int b, int p)
{
    LL res = 1;
    while (b)
    {
        if (b & 1) res = res * a % p;
        
        b >>= 1;
        a = (LL)a * a % p;
    }
    
    return res;
}

int main()
{
    int n;
    scanf("%d", &n);
    
    while (n -- )
    {
        int a, b, p;
        scanf("%d%d%d", &a, &b, &p);
        
        printf("%lld\n", fast_power(a, b, p));
    }
    
    return 0;
}

标签:d%,int,res,LL,875,long,fast,快速,AcWing
From: https://blog.51cto.com/u_16170343/7254007

相关文章

  • kubernetes client-go快速入门及源码阅读
    client-go是kubernetes官方维护的一个go语言客户端,用于与k8s集群交互,使用client-go可以很方便的完成k8s的二次开发(似乎也必不可少),无论是稳定性还是健壮性都有充分的保障。client-go代码版本:v0.20.2个人水平有些,一定会出现不严谨或者错误的地方,如有错误麻烦评论指正,谢谢版......
  • 稀疏矩阵的压缩存储及转置,快速转置法,C++代码实现
    /*稀疏矩阵的压缩存储及转置*/#include<iostream>usingnamespacestd;/*三元组顺序表的类型定义*/#defineitemSize100typedefstruct{introw,col;intitem;}thNode;typedefstruct{thNode*data;//data[0]不用intm,n,t;//分别表示行数、列......
  • 如何批量转换图片格式(jpg,png,gif,bmp),一招教你快速搞定
    工具一.作图狗www.huahaotu.com作图狗是一款非常好用的在线图像批量处理编辑网站,支持将图片批量裁剪、压缩、拼图、转换格式、图片转文字等,还支持给图片添加文字、图片水印,批量处理,节省频繁操作的时间。    工具二:电脑自带工具软件介绍:除了使用其他软件来转换图......
  • AcWing 873. 欧拉函数
    题目给定$n$个正整数$a_i$,请你求出每个数的欧拉函数。欧拉函数的定义$1∼N$中与$N$互质的数的个数被称为欧拉函数,记为$\varphi(N)$。若在算数基本定理中,$N={p_1}^{a_1}{p_2}^{a_2}...{p_m}^{a_m}$,则:$\varphi(n)=m(1-1/p_1)(1-1/p_2)...(1-1/p_k)$输入格式第......
  • ASEMI-APT80DQ40BG二极管快速恢复特性及应用
    编辑-Z本文主要介绍了APT80DQ40BG二极管的快速恢复特性以及应用。首先,对该二极管的结构和工作原理进行了简要介绍。接着,详细阐述了其快速恢复特性及其在电源、逆变器和电动汽车等领域的应用。最后,对APT80DQ40BG二极管的优点和未来发展进行了总结归纳。 1、APT80DQ40BG二极管的结构......
  • 引导滤波(guided filter)与快速引导滤波(fast guided filter)理解
    最近在学习图片的滤波和去噪的相关知识,查阅了一些资料参考了一些博客,这里做一个整合+理解。参考的博客资料在文末。引入普通滤波的概念假设输入图像为p,滤波窗口为wk,经过滤波后的输出图像为q,那么q图的第i个像素是由输入图p中以第i个像素为中心的窗口内的所有像素加权平均得......
  • 用 plantUML 快速绘制 UML 图
    用plantUML快速绘制UML图UML(统一建模语言)是一种用于软件开发中的可视化建模语言,它可以帮助我们描述系统的结构、行为和交互等方面。UML包括了多种不同的图,例如类图、时序图、用例图等,每种图都有自己的符号和规则。但是,要用传统的绘图工具来画UML图,可能会比较繁琐和耗时,而......
  • ASEMI-APT80DQ40BG二极管快速恢复特性及应用
    编辑-Z本文主要介绍了APT80DQ40BG二极管的快速恢复特性以及应用。首先,对该二极管的结构和工作原理进行了简要介绍。接着,详细阐述了其快速恢复特性及其在电源、逆变器和电动汽车等领域的应用。最后,对APT80DQ40BG二极管的优点和未来发展进行了总结归纳。 1、APT80DQ40BG二极管的......
  • PyQt 快速使用
    1.安装PyQt:使用pip命令在终端或命令提示符中运行以下命令:pipinstallpyqt52.创建PyQt应用程序:导入PyQt5模块并创建一个QApplication实例。importsysfromPyQt5.QtWidgetsimportQApplication,QMainWindowapp=QApplication(sys.argv)window=QMainWindow()......
  • 一次搞定:借助Hutool封装代码快速解决webservice调用烦恼
    前言相信很多同行哪怕学了许多主流技术,但工作上依然免不了和传统企业打交道,而这样的企业往往还在用webservice做接口交互。本文是作者近两年和医疗行业的厂家打交道研究出来的一点调用webservice接口的心得,代码在生产环境也用了挺久了,专门捞出来作为一期干货分享给大家。......