本文主要是介绍2023山东ICPC省赛Problem E. Math Problem,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
2023 山东 I C P C 省赛 P r o b l e m E . M a t h P r o b l e m \Huge{2023山东ICPC省赛Problem E. Math Problem} 2023山东ICPC省赛ProblemE.MathProblem
文章目录
- 题意
- 思路
- 标程
比赛链接:Dashboard - The 13th Shandong ICPC Provincial Collegiate Programming Contest - Codeforces
官方题解:E - 数学问题 - SUA Wiki
题意
首先给出五个数字: n , k , m , a , b n,k,m,a,b n,k,m,a,b;然后可以对n执行进行以下两种操作任意次:
- 选择一个整数 x ( 0 ≤ x ≤ k ) x(0 \le x \le k) x(0≤x≤k);令 n = k × n + x n=k\times n + x n=k×n+x,该操作每次花费 a a a枚金币,每次选择的 x x x可以不同。
- 令$n=\left \lfloor \frac{n}{k} \right \rfloor ,该操作每次花费 ,该操作每次花费 ,该操作每次花费b$枚金币。
求将 n n n变为** m m m的倍数**最少需要花费几枚金币( 0 0 0是任何正整数的倍数)。
数据范围:
- ( 1 ≤ n ≤ 1 0 18 1\leq n\leq 10^{18} 1≤n≤1018, 1 ≤ k , m , a , b ≤ 1 0 9 1\leq k, m, a, b\leq 10^9 1≤k,m,a,b≤109)
思路
跟据两种操作,我们会发现,若执行一次操作①后,再执行一次操作②;那么这两次操作可以相互抵消, n n n的值不变。
因此我们会发现,执行完操作①之后将不再会执行操作②。
跟据题目数据范围可知,操作①和操作②之和不会超过 200 200 200次,是比较小的。然后跟据上面的结论,我们可以暴力枚举先执行操作②的次数。
由于操作①有+x
的情况,因此进行 p p p次操作①后, n n n的范围为: [ k p × n 0 , k p × ( n 0 + 1 ) − 1 ] [k^p\times n_0,k^p\times (n_0+1)-1] [kp×n0,kp×(n0+1)−1](其中 n 0 n_0 n0是 n n n完成除法操作时的值),因此只要 n n n在此区间即可停止乘法操作。
需要注意的是,在枚举的过程中,答案可能会超过long long
范围,因此需要使用__int128
(__int128
无法直接读入和输出,只能使用快读读入)。
其实我们在计算 n n n的范围时,只需要将其对 m m m取模即可,因为我们只需要判断当前 n n n的值距离 m m m的倍数的距离即可。
标程
#include<bits/stdc++.h>using namespace std;#define IOS ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
#define int long long
#define ULL unsigned long long
#define PII pair<int, int>
#define lowbit(x) (x & -x)
#define Mid ((l + r) >> 1)
#define ALL(x) x.begin(), x.end()
#define endl '\n'
#define fi first
#define se secondconst int INF = 0x7fffffff;
const int Mod = 1e9 + 7;
const int N = 2e5 + 10; void Solved() { int n, k, m, a, b; cin >> n >> k >> m >> a >> b;if(n % m == 0) {cout << "0\n"; return;}if(k == 1) {cout << "-1\n"; return;}int res = 1e18, cost = 0;//双重循环,第一层枚举除的次数,第二层枚举乘的次数while(1) {int base = n % m, p = 1;for(int i = 0; ; i ++ ) {int d = (m - base) % m;//需要对m取模,表示距离每个m的倍数的位置// int d = m - base;// if(d == m) d = 0;if(d < p) {res = min(res, cost + i * a);break;}base = base * k % m;p = p * k;//对于x的累加不需取模}if(n == 0) break;n /= k;cost += b;}cout << res << endl;
}signed main(void) {IOSint ALL = 1; cin >> ALL;while(ALL -- ) Solved();// cout << fixed;//强制以小数形式显示// cout << setprecision(n); //保留n位小数return 0;
}
这篇关于2023山东ICPC省赛Problem E. Math Problem的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!