Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- ∧_∧
- ( ・ω・。)つ━☆・*。
- ⊂ ノ ・゜
- しーJ Accepted
- */
- // #pragma GCC optimize("O3")
- // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
- #include <bits/stdc++.h>
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>
- #define ll long long
- #define all(x) begin(x), end(x)
- #define x first
- #define y second
- #define int long long
- using namespace std;
- using namespace __gnu_pbds;
- typedef long double ld;
- template<typename T>
- using kawaii_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
- const ld PI = atan2(0, -1);
- void seriy() {
- ios::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- cout << fixed << setprecision(14);
- #ifdef _offline
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- }
- const int MAXN = 1e6 + 10;
- const int MAXM = 600;
- const int INF = 1e18 + 7;
- const int BASE = 47;
- const int MOD = 1e9 + 7;
- const int MAXLOG = 61;
- const ld EPS = 1e-6;
- string out(int n, string c) {
- string k = "";
- for(int i = 0; i < n - 1; i++) {
- k += c + "*";
- }
- k += c;
- return k;
- }
- signed main() {
- seriy();
- // cerr << (1ll << 59) - 2 << " ";
- string ans = "";
- string ans2;
- ans2.resize(1001);
- int n, d;
- cin >> n >> d;
- int nn = n;
- string k;
- k += (d + '0');
- if(n % d == 0) {
- if(d != 1) {
- vector<int> pw;
- pw.push_back(1);
- while(pw.back() <= 1e18) {
- pw.push_back(pw.back() * d);
- }
- int cur = 0;
- for(int i = pw.size() - 1; i > 0; i--) {
- if(n >= pw[i]) {
- n -= pw[i];
- cur += pw[i];
- ans += out(i, k);
- if(n != 0) {
- ans += "+";
- }
- }
- else {
- int now = cur + pw[i];
- int diff = now - nn;
- string succ = "";
- succ += out(i, k);
- for(int j = i; j > 0; j--) {
- if(diff >= pw[j]) {
- diff -= pw[j];
- succ += "-";
- succ += out(j, k);
- }
- }
- // cerr << now << " " << succ << '\n';
- if(ans.size() + succ.size() < ans2.size()) {
- ans2 = ans;
- if(ans.size() != 0) ans2 += "+";
- ans2 += succ;
- }
- }
- }
- }
- else {
- if(n < 1e6) {
- for(int i = 0; i < n - 1; i++) {
- ans += "1+";
- ans2 += "1+";
- }
- ans += "1";
- ans2 += "1";
- }
- }
- }
- else {
- ans = "no solution";
- ans2 = "no solution";
- }
- // assert(ans.size() <= 1000 || d == 1);
- if(ans2.size() <= 1000) cout << ans2;
- else if(ans.size() <= 1000) cout << ans;
- else cout << "no solution";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement