专栏首页mlNYOJ----次方求模

NYOJ----次方求模

次方求模

时间限制: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

一眼就可以看到,数据很大,对于O(n)的时间复杂度,显然是过不了的....采用乘方去模的。。。比采用快速求幂要好的多.....贴下代码吧!!

#include<iostream>
using namespace std;
int main()
{
    long long  n, a,b,c,ans;
       cin>>n;
   while(n--)
   {
       cin>>a>>b>>c;
       a%=c;
       ans=1;
       while(b)
       {
         if(b&1)
         {
             ans*=a;
             ans%=c;
         }
         a*=a;
         a%=c;
         b>>=1;
       }
       cout<<ans<<endl;
   }
   return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • HDUOJ-----2065"红色病毒"问题

    "红色病毒"问题 Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (...

    Gxjun
  • HDUOJ----(2064)汉诺塔III

    汉诺塔III Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Ja...

    Gxjun
  • HDUOJ-------(1211)RSA

    RSA Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/...

    Gxjun
  • Gym 100952H&&2015 HIAST Collegiate Programming Contest H. Special Palindrome【dp预处理+矩阵快速幂/打表解法】

    H. Special Palindrome time limit per test:1 second memory limit per test:64 mega...

    Angel_Kitty
  • 剑指offer——丑数

    题目描述 把只包含质因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含质因子7。 习惯上我们把1当做是第一个丑...

    AI那点小事
  • 勾股数组

          一般地,若三角形三边长a,b,c都是正整数,且满足a,b的平方和等于c的平方,那么数组(a,b,c)称为勾股数组。勾股数组是人们为了解出满足勾...

    Ch_Zaqdt
  • 开始使用Octave

    mwangblog
  • LeetCode 67. 二进制求和

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/add-binary 著作权归领扣网络所有。商业转载...

    Michael阿明
  • 【Gym 100947C】Rotate It !!

    饶文津
  • 【UVA 11401】Triangle Counting

    以i 为最大边,第二边为i-1、i-2、...2 的三角形分别有 i-2个、i-3、... 、1个,总共就有(i-1)*(i-2)/2个。有(i-1)/2条边算...

    饶文津

扫码关注云+社区

领取腾讯云代金券