a^b-白红宇

a^b

阅读量：414 次

发布时间：2019-03-06

本文共 487 字，大约阅读时间需要 1 分钟。

题目描述

求 a 的 b 次方对 p 取模的值。

输入格式

三个整数 a,b,p ,在同一行用空格隔开。

输出格式

输出一个整数，表示a^b mod p的值。

数据范围

1≤a,b,p≤$10^{9}$

输入样例：

3 2 7

输出样例：

大致思路：任何一个数都可以写成

\[n = 2^{p_1} + 2^{p_2} + 2^{p_3} \cdots\]

其中$p_i$为非负整数，所以可以利用二分把这题算法复杂度降低到logn

#include 
   
    using namespace std;int main(){    int a, b, p;    cin >> a >> b >> p;    int res = 1 % p;    while (b)    {        if (b & 1)            res = res * 1ll * a % p;        a = a * 1ll * a % p;        b >>= 1;    }    cout << res << endl;    return 0;}

转载地址：http://qktkz.baihongyu.com/

你可能感兴趣的文章

MySQL SQL 优化指南：主键、ORDER BY、GROUP BY 和 UPDATE 优化详解

查看>>

MYSQL sql语句针对数据记录时间范围查询的效率对比

查看>>

mysql sum 没返回,如果没有找到任何值，我如何在MySQL中获得SUM函数以返回'0'？

查看>>

mysql Timestamp时间隔了8小时

查看>>

Mysql tinyint(1)与tinyint(4)的区别

查看>>