欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

各种快速幂(qaq)

程序员文章站 2023-09-08 23:45:03
今天分享下各种快速幂(有点坑) ......

   今天分享下各种快速幂(有点坑)

第一种方法(普通的快速幂)   
#include<iostream> //适用范围a,b,p 1+9e #include<cmath> #include<algorithm> #include<stack> #include<map> using namespace std; typedef long long ll; ll fastpower(ll a,ll b,ll p) //写一个快速幂的函数 { ll ans = 1; while(b) //b的二进制还有位数 { if(b & 1) //b为奇数 循环 { ans = ans * a % p; } a = a * a % p; // 2^n 增长 b >>= 1; // b右移一位 } return ans % p; //防止b为0,而没有模 p } int main() { ll a,b,p; cin>>a>>b>>p; cout<<fastpower(a,b,p)<<endl; return 0; }
第二种方法(第一种的强化版)
#include <stdio.h> //无敌的_int 128 可以无视a,b,p的范围,这范围真的恶心 a,b,p 1+18e typedef __int128 ll; longlong a_b_mod_c(ll a, ll b, ll p)
{ ll s = 1; while (b)
{ if (b & 1) s = (s * a) % p; a = (a * a) % p; b >>= 1; } return (longlong) s % p; } int main()
{ int t; longlong a, b, p; scanf("%d", &t); while (t--)
{ scanf("%lld%lld%lld", &a, &b, &p); printf("%lld\n", a_b_mod_c(a, b, p)); } return0; }
第三种方法(普通快速幂的优化,即也用了快速乘)
#include <iostream> using namespace std; typedef long long ll; ll q_mul(ll a, ll b, ll mod) //快乘
{ ll ans=0; while(b)
{ if(b & 1) ans=(ans+a)%mod; a=(a<<1)%mod; b>>=1; } return ans; } ll q_pow(ll a, ll b, ll mod) //快幂
{ ll ans=1; while(b)
{ if(b & 1) ans=q_mul(ans,a,mod); a=q_mul(a,a,mod); b>>=1; } return ans; } int main()
{ ll a,b,mod; int n; cin>>n; while(n--) { cin>>a>>b>>mod; cout<<q_pow(a,b,mod)<<endl; } }
java代码
import java.math.biginteger; import java.util.scanner; public class main{ public static void main(string[] args)
{ scanner sc = new scanner(system.in); int n = sc.nextint(); for (int i = 0; i < n; i++)
{ biginteger a = sc.nextbiginteger(); biginteger b = sc.nextbiginteger(); biginteger p = sc.nextbiginteger(); system.out.println(a.modpow(b, p)); } } }
最后的大招-python(变态,一般做大数的都用它,别问我为什么,
一时用python一时爽,一直用python一直爽,貌似是py的整数类的封装问题)
python

1,def fastexpmod(b, e, m): result = 1 while e != 0: if (e&1) == 1: # ei = 1, then mul result = (result * b) % m e >>= 1 # b, b^2, b^4, b^8, ... , b^(2^n) b = (b*b) % m return result t=int(input()) while t: t-=1 a, b, c = map(int, input().split()) print(fastexpmod(a,b,c))

2,n = int(input()) for i in range(n): a, b, p = map(int, input().split()) print(pow(a, b, p))

如果有错误的地方恳请大家指出来。

 

1≤t≤1031≤t≤103,1≤a,b,p≤1018

上一篇: c++基础STL

下一篇: linux 学习第八天