c++ - 计算 a^b^c mod 10^9+7
问题描述
问题链接 - https://cses.fi/problemset/task/1712
输入 -
1
7
8
10
- 预期产出 -
928742408
- 我的输出 -
989820350
让我感到困惑的一点 - 在 100 个输入中,仅在 1 或 2 个测试用例中,我的代码提供了错误的输出,如果代码错误,它不应该为所有内容提供错误的输出吗?
我的代码 -
#include <iostream>
#include <algorithm>
typedef unsigned long long ull;
constexpr auto N = 1000000007;
using namespace std;
ull binpow(ull base, ull pwr) {
base %= N;
ull res = 1;
while (pwr > 0) {
if (pwr & 1)
res = res * base % N;
base = base * base % N;
pwr >>= 1;
}
return res;
}
ull meth(ull a, ull b, ull c) {
if (a == 0 && (b == 0 || c == 0))
return 1;
if (b == 0 && c == 0)
return 1;
if (c == 0)
return a;
ull pwr = binpow(b, c);
ull result = binpow(a, pwr);
return result;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
ull a, b, c, n;
cin >> n;
for (ull i = 0; i < n; i++) {
cin >> a >> b >> c;
cout << meth(a, b, c) << "\n";
}
return 0;
}
`
解决方案
您的解决方案基于不正确的数学假设。如果你想计算 a b c mod m 你不能减少指数 b c mod 10 9 +7。换句话说,a b c mod m != a b c mod m mod m。相反,您可以减少它 mod 10 9 +6 ,因为费马小定理有效。因此,您需要在不同的模数下计算指数 b c 。
推荐阅读
- javascript - Apollo 奇怪地改变了查询结果
- spring - 如何在春季阻止音频(麦克风)控制
- ios - 为什么 UITableViewCell 相互重叠?
- scala - Spark Scala 编码器案例类
- c++ - python3如何使用protobuf的cpp生成代码实现?
- sql - 按月填补日期空白
- windows - Windows Server - 在断开许多 RDP 会话时使用默认 rdp 许可证 2 会使 RD 服务繁忙
- pandas - 在没有 pip 的情况下安装 pandas
- python - Python Dict 覆盖以前的列表
- javascript - 如何处理节点错误“未处理的承诺拒绝”,以便无论如何加载页面?