FZU Super A^B mod C（欧拉函数降幂）-白红宇

FZU Super A^B mod C（欧拉函数降幂）

阅读量：5038 次

发布时间：2019-06-12

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

Problem 1759 Super A^B mod C

Accept: 878 Submit: 2870
Time Limit: 1000 mSec Memory Limit : 32768 KB

Problem Description

Given A,B,C, You should quickly calculate the result of A^B mod C. (1<=A,C<=1000000000,1<=B<=10^1000000).

Input

There are multiply testcases. Each testcase, there is one line contains three integers A, B and C, separated by a single space.

Output

For each testcase, output an integer, denotes the result of A^B mod C.

Sample Input

      3 2 4 

      2 10 1000 

Sample Output

1

24

Source

FZU 2009 Summer Training IV--Number Theory

题目链接：

参考博客：，本来在搞蛇精病的十进制快速幂的时候做的这个，结果超时了，后来测试发现十进制快速幂还没二进制快……是我太天真了……于是膜一下正确解法，主要利用了这个欧拉定理的扩展公式，当然最重要的是求出一个数的欧拉函数值$phi(x)$，这个可以用埃式筛的思想求得。

代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   using namespace std;#define INF 0x3f3f3f3f#define LC(x) (x<<1)#define RC(x) ((x<<1)+1)#define MID(x,y) ((x+y)>>1)#define CLR(arr,val) memset(arr,val,sizeof(arr))#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);typedef pair
                    
                      pii;typedef long long LL;const double PI = acos(-1.0);const int N = 1000010;LL bpow(LL a, LL b, LL mod){ LL r = 1LL; while (b) { if (b & 1) r = ((r % mod) * (a % mod)) % mod; a = ((a % mod) * (a % mod)) % mod; b >>= 1; } return r;}LL phi(LL n){ LL r = n, sz = sqrt(n); for (LL i = 2; i <= sz; ++i) { if (n % i == 0) { r = r * (i - 1) / i; while (n % i == 0) n /= i; } } if (n > 1) r = r * (n - 1) / n; return r;}int main(void){ LL a, c; char B[N]; while (~scanf("%I64d%s%I64d", &a, B, &c)) { LL phi_c = phi(c); int len = strlen(B); LL b; if (len <= 20) { sscanf(B, "%I64d", &b); if (b >= phi_c) b = b % phi_c + phi_c; } else { b = 0LL; for (int i = 0; i < len; ++i) { b = b * 10LL + B[i] - '0'; if (b > phi_c) b %= phi_c; } b += phi_c; } printf("%I64d\n", bpow(a, b, c)); } return 0;}

转载于:https://www.cnblogs.com/Blackops/p/6414134.html

你可能感兴趣的文章