hihocoder1777 彩球

思路：

记录一下快速幂计算过程中爆long long的两种解决方法：

1. 使用__int128，这玩意本地编译不通过，提交OJ能AC。

实现：

 #include <bits/stdc++.h>

 using namespace std;

 typedef long long LL;

 __int128 qpow(__int128 a, __int128 b, __int128 mod)

 {

     __int128 ret = 1LL;

     while (b)

     {

         if (b & ) ret = ret * a % mod;

         a = a * a % mod;

         b >>= ;

     }

     return ret;

 }

 int main()

 {

     LL n, k, P;

     scanf("%lld %lld %lld", &n, &k, &P);

     LL ans = qpow(k, n, P);

     printf("%lld\n", ans);

     return ;

 }

2. 利用和快速幂类似的思想实现如下不会溢出的乘法操作。

实现：

 #include <bits/stdc++.h>

 using namespace std;

 typedef long long LL;

 LL n, k, p;

 LL mul(LL a, LL b)

 {

     LL ans = ;

     while (b)

     {

         if (b & ) ans = (ans + a) % p;

         a = (a + a) % p;

         b = b >> ;

     }

     return ans;

 }

 LL Pow(LL a, LL b)

 {

     LL result = ;

     LL base = a % p;

     while (b)

     {

         if (b & ) result = mul(result, base) % p;

         base = mul(base, base) % p;

         b = b >> ;

     }

     return result;

 }

 int main()

 {

     cin >> n >> k >> p;

     cout << Pow(k, n) << endl;

     return ;

 }

巴特西

hihocoder1777 彩球

最新文章

热门文章