快速幂

朴灿烈づ我的快乐病毒、 2022-06-11 00:51 39阅读 0赞

集训进行了将近2个礼拜，这段时间以恢复性训练为主，我一直在密切关注大家的训练情况，目前为止，对大家的表现相当满意，首先是绝大部分队员的训练积极性很高，其次，都很遵守集训纪律，最后，老队员也起到了很好的带头作用，这里特别感谢为这次DP专题练习赛提供题目和测试数据的集训队队长xhd同学.  
  
特别高兴的是，跟随集训队训练的一批新队员表现非常好，进步也比较显著，特别是训练态度大大超出我的预期，我敢说，如果各位能如此坚持下去，绝对前途无量！  
  
考虑到新队员还没有经过系统训练，我这里特别添加一道简单题：  
给定三个正整数A，B和C（A,B,C<=1000000），求A^B mod C的结果.  
  
希望各位都能体会到比赛中AC的快乐，绝对的量身定制，很高的待遇哟，呵呵...

Input

输入数据首先包含一个正整数N,表示测试实例的个数，然后是N行数据，每行包括三个正整数A,B,C。

Output

对每个测试实例请输出计算后的结果，每个实例的输出占一行。

Sample Input

3
    2 3 4
    3 3 5
    4 4 6

Sample Output

0
    2
    
       
        4
       
        用long long 才能过，套用快速幂模板即可
       
        
       
        #include <cstdio>
    #include <algorithm>
    using namespace std;
    long long A(long long n,long long m,long long k)
    {
        long long sum=1;
        n%=k;
        while(m)
        {
            if(m&1)
                sum=(sum*n)%k;
            n=(n*n)%k;
            m/=2;
        }
        return sum;
    }
    int main()
    {
        long long a,b,c;
        int n;
        scanf("%d",&n);
        while(n--)
        {
             scanf("%lld %lld %lld",&a,&b,&c);
             printf("%lld\n",A(a,b,c));
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，39人围观）

还没有评论，来说两句吧...

相关阅读

相关快速幂

快速幂模板第一种(最简单) //快速幂模板 (a的b次方)%c结果此处使用long类型是防止整型溢出 long pow(int a,int b

短命女/ 2023年01月11日 09:11/ 0 赞/ 6 阅读

相关快速幂，矩阵快速幂（模板）

1，整数快速幂： C++ Code <table style="width:100%;font-family:Consolas, 'Courier New';font-

左手的ㄟ右手/ 2022年06月11日 03:57/ 0 赞/ 297 阅读

相关快速幂

集训进行了将近2个礼拜，这段时间以恢复性训练为主，我一直在密切关注大家的训练情况，目前为止，对大家的表现相当满意，首先是绝大部分队员的训练积极性很高，其次，都很遵守集训纪律，最

朴灿烈づ我的快乐病毒、/ 2022年06月11日 00:51/ 0 赞/ 40 阅读

相关快速幂和矩阵快速幂

前言新年第一篇技术类的文章，应该算是算法方面的文章的。看标题：快速幂和矩阵快速幂，好像挺高大上。其实并不是很难，快速幂就是快速求一个数的幂（一个数的 n 次方）。

╰+攻爆jí腚メ/ 2022年06月01日 08:10/ 0 赞/ 288 阅读

相关矩阵快速幂+整数快速幂

嗯~ 今天总结一下快速幂的知识点 1.首先讲一下矩阵相乘矩阵A与矩阵B相乘的前提条件：A矩阵的列必须和矩阵B的行相等。若A矩阵是m\p的矩阵，那么B矩阵必定是p\n的

缺乏、安全感/ 2022年05月11日 13:22/ 0 赞/ 324 阅读

相关快速幂

快速幂快速幂，实际上是快速幂取模的缩写。简单的说，就是快速的求一个幂式的模(余)。在程序设计过程中，经常要去求一些大数对于某个数的余数，为了得到更快、计算范围更大的算法

刺骨的言语ヽ痛彻心扉/ 2022年04月17日 05:29/ 0 赞/ 234 阅读

相关快速幂

快速求幂能将a^b 的时间复杂度从O(n) 降到O(logn) 核心思想利用二进制详细：[http://www.cnblogs.com/CXCXCXC/p/

╰+攻爆jí腚メ/ 2022年04月11日 11:51/ 0 赞/ 282 阅读

相关快速幂

快速幂求法 void quick(int a,int b){ int ans=1,base=a; while(b){ if(b&1)a

谁践踏了优雅/ 2022年03月20日 05:28/ 0 赞/ 254 阅读

相关快速幂

快速幂的思想就是将幂指数转化为2进制再来运算例子：\\(a^5\\,\\,\\,\\,5=101\\,\\,\\, a^5=a^1\a^4\\) 时间复杂度\\(O(lo

古城微笑少年丶/ 2021年12月21日 15:25/ 0 赞/ 240 阅读

相关快速幂

快速幂：将幂指数 b 转换为二进制，例：6 对应二进制为 110，此时 a b =a4a2a0，时间复杂度为 f（n）=lgn public class QuickP

忘是亡心i/ 2021年09月21日 05:32/ 0 赞/ 393 阅读