华华教月月做数学

https://ac.nowcoder.com/acm/problem/23046

快速幂

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

找到了心仪的小姐姐月月后，华华很高兴的和她聊着天。然而月月的作业很多，不能继续陪华华聊天了。华华为了尽快和月月继续聊天，就提出帮她做一部分作业。
月月的其中一项作业是：给定正整数A、B、P，求 $A^B\mod P$ 的值。华华觉得这实在是毫无意义，所以决定写一个程序来做。但是华华并不会写程序，所以这个任务就交给你了。
因为月月的作业很多，所以有T组询问。

输入描述:

第一行一个正整数T表示测试数据组数。
接下来T行，每行三个正整数A、B、P，含义如上文。

输出描述:

输出T行，每行一个非负整数表示答案。

示例1

输入

复制

2
2 5 10
57284938291657 827493857294857 384729583748273

输出

复制

2
18924650048745

备注:

，

1、可以__int128避免爆ll
2、改用龟速乘，也可以避免爆ll，py的话……但我没说。

C++


#include<bits/stdc++.h>
using namespace std;
#define ll long long

__int128 qpow(__int128 a, __int128 n, __int128 mod) {
    __int128 ret = 1;
    while (n) {
        if (n & 1)
            ret = ret * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return ret;
}
int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        ll a, b, p;
        scanf("%lld%lld%lld", &a, &b, &p);
        printf("%lld\n", (ll)qpow((__int128)a, (__int128)b, (__int128)p));
    }
    return 0;
}

Python

T = int(input())
for _ in range(T):
    a,b,c = map(int,input().split())
    print(pow(a,b,c)) #py的help可以康康pow的函数自带快速幂

牛客算法竞赛入门课文章被收录于专栏

给雨巨打call

全部评论

推荐最新楼层

💭💡🎈风中追风

西北工业大学 C++

蒟蒻想问一下为啥—int128 在codeblock上编译不了

点赞回复分享

发布于 2020-07-14 15:03

02-21 16:31

长沙理工大学

双非本科软工大四学了C/C++和Qt，春招在即是深入服务端还是主攻QT开发？

大家好，今天分享一个很贴合目前校招时间段的提问：Up你好，本人双非本科大四，软件工程专业。大学前两年因为感觉前端好学，岗位也多选择学习前端。但那时比较懒散，课也多，所以前端也没有学多好。后来互联网寒冬，觉得出去不好找工作。就在大三下开始准备考研，但在去年10月份放弃考研（因为家里的一些事故，一个半月没有复习考研），处理好后，剩70多天感觉考不上值得上的学校。所以干脆准备就业，但感觉前端这个方向特别凉，于是换成了Linux c++方向（为此拒绝了一个前端实习）10月底到现在复习了c语言，学习了C++语法，特性，包括STL这些。学习了Linux系统编程进程线程，网络编程tcp/udp，多路转接，l...

牛客230000345号：毕业入坑两年，提点参考的东西吧，建议边找边备研，学历才是第一生产力，后期如果你要职业发展，这是最基本的几个了，工作和晋升除了项目经验，不就是比的派个人学历、吹牛能力和一堆头衔了(晋升的话，派系很重要)。工作方面，不了解服务端，但是你可以看招聘，其实相比来说qt在客户端和服务端都可以用到，而且跨平台兼容性好，而且qt不就是c+++吗(学好c++，用哪个框架都不头痛)，qt不只是给你个UI界面，封装的很多东西都是可以借鉴的。看你想去哪个城市，现在长沙软件行情不好，真心建议没上岸可以去深圳看看，长沙这边工资对标深圳砍半(眼泪流下来)，长沙不少大一点私企面试的也开始卷学历卷项目(双非泪奔)，如果想去国企你要能吹当然也可以(其实国企也就那12%的公积金了，并不稳定，但是稳定穷是肯定的)。想去好一点的，建议把基础打牢，学历一定要提高(长期发展一定要，国内还是不少地方学历论的)，如果有实习期建议能参与公司项目就参与，不然只会被拷打，最好从项目或者demo里把设计模式、指针、特性、模板、多线程实现并发并行、通讯协议、数据库这些基本的学会一部分，建议再学学qml和Linux，最好学一点嵌入式(Linux用在嵌入式板挺多的)，掌握一门脚本语言(Python，Python，Python)和git或者svn代码管理，没签合同(不是三方)，你还是校招生，校招只有一次(当然也可以说是本科一次，硕士一次，博士一次)，用了错过就没有了，好多公司最喜欢招应届生了，一张白纸(又便宜又容易被PUA)。最后，其实纠结这么多，不如第一份工作就选你最喜欢的编程语言、框架和操作系统，反正都是牛马，也不一定只吃一家喂的草