题目大意
给定 \(n,k,m,a,b\)，两种操作：
- 花费 \(a\)，将 \(x\) 变为 \(x \times k\)
- 花费 \(b\)，将 \(x\) 变为 \(\lfloor x/k \rfloor\)
求最小代价使 \(x\) 变为 \(m\) 的倍数，不能则输出 \(-1\)。
关键性质
- k 进制视角：乘 \(k\) = 左移一位，除 \(k\) = 右移一位
- 顺序无关：操作顺序不影响最终结果（只取决于次数）
解题思路
枚举除法次数 \(t\)，设 \(cur = \lfloor n/k^t \rfloor\)。
对于固定的 \(cur\)，我们需要最小乘法次数 \(s\)，使得存在 \(Y < k^s\) 满足：
\[(cur \times k^s + Y) \equiv 0 \pmod{m}
\]
设 \(r = (m - cur \times k^s \bmod m) \bmod m\)，则条件等价于：
\[r < k^s
\]
从小到大枚举 \(s\)，找到第一个满足条件的即可。
总代价 = \(t \times b + s \times a\)，取最小值。
代码
#include <bits/stdc++.h>
#include <queue>
using ll = long long;
using namespace std;
const int N = 1e5 + 10, mod = 998244353, inf = 0x3f3f3f3f;
ll n, a, m, k, b;
void solve() {cin >> n >> k >> m >> a >> b;if (n % m == 0) {cout << 0 << '\n';return;}if (k == 1) {cout << -1 << '\n';return;}ll cur = n, ans = inf;ll cntb = 0, cnta, kk;ll num;while (1) {if (cntb * b > ans) break; // 剪枝优化ll kk = 1;ll cost;cnta = 0;ll x = (m - cur % m) % m;while (1) { // 每一个cur都算一遍cntaif (x < kk) {cost = b * cntb + a * cnta;break;}x = (x * k) % m;kk = kk * k;cnta++;}ans = min(cost, ans);if (cur == 0) break; // 不能再除了跳出cur /= k;cntb++;}cout << ans << '\n';
}
int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int _ = 1;// cin >> _;while (_--) {solve();}return 0;
}