自动搬运

查看原文

来自洛谷，原作者为

	AnteAntibe Moonlight illuminate me, Promise is coming true.

搬运于2025-08-24 22:12:40，当前版本为作者最后更新于2025-08-21 20:22:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P5623 [Celeste-A] Sever the Skyline

随机挑题，写掉之后发现竟然没有题解！于是前来水咕值。

Description

题意大概是这样：给出三个数 $p ,q ,n$，构造一组数字，每一项都可以用 $p^i\times q^j$ 表示并且和为 $n$。同时要求这一组数的任意两个数之间不能有倍数关系。

Solution

首先观察一组合法的构造需要满足什么性质。
核心的约束显然是“不能有倍数关系”这一条。用 $p^i \times q^j$ 表示一个数的话，如果一个数的 $i$ 和 $j$ 同时比另一个大的话，这两个数就有倍数关系了。

所以如何避免这件事情呢？思考一个直观的做法！我们让 $i$ 单调递增，$j$ 单调递减。现在我们要做的就是构造这样的一组合法解。

乍一看很像数学题啊！但是稍微思考一下就发现：同时具有幂、加法、乘法操作，很难找到数字之间的关系。无迹可寻的时候就考虑暴力吧！

假定 $p > q$，如果当前数是 $p$ 的倍数，就把这个数整个除以 $p$，然后寻找一个最大的 $q^j$ 使得 $p \mid (n - q^j )$ 然后继续将 $n$ 除以 $q$，周而复始。假设一个数被除了 $t$ 次 $p$，答案的序列就是每次操作的 $q^j \times p^t$。
由于每次除以了 $p$，这就自动保证了 $i$ 的单调递增。但是 $j$ 的单调递减无法保证，所以需要在每次记录这次选的 $j$ 为 $lastj$，在下一次枚举 $j$ 的时候从 $lastj - 1$ 枚举到 $0$ 即可。这样就可以保证 $j$ 的单调递减了。

写一个搜索，在最后 $n$ 为 $0$ 的时候输出序列即可。

注意：$p > q$，倒序遍历。

code:

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 1e5 + 10;
ll p ,q ,n ,maxx ,thi;

inline ll ksm(ll base ,ll p) {
    ll res = 1;
    for(;p>0;) {
        if(p % 2) {
            res *= base;
            res = res;
        }
        p >>= 1;
        base = base * base;
    }
    return res;
}

ll ans[N] ,flag;

inline void dfs(ll res ,ll la ,ll num ,ll iidx) { //num 需要 乘回来的数
    if (flag) {
        return;
    }
    if (res == 0) {
        for (register int i=iidx-1 ;i>=1 ;i--) {
            if (i != 1) {
                printf("%lld " ,ans[i]);
            }
            else {
                printf("%lld" ,ans[i]);
            }
        }
        flag = 1;
        return;
    }
    if (res%p == 0) {
         ans[iidx] *= p;
         dfs(res/p ,la ,num*p ,iidx);
    }
    for (register int i=la ;i>=0 ;i--) {
        thi = ksm(q ,i);
        if ((res - thi) % p == 0) {
            if (res < thi) {
                continue;
            }
            ans[iidx] = num * thi;
            dfs((res - thi)/p ,i-1 ,num*p ,iidx+1);
            ans[iidx] = 0;
        }
    }
}

int main() {
    int T;
    scanf("%d" ,&T);
    for (;T--;) {
        scanf("%lld %lld %lld" ,&n ,&p ,&q);
        if (p < q) {
            swap(p ,q);
        }
        // init 
        ll tmp = n;
        maxx = 0;
        thi = 1;
        flag = 0;
        for (register int i=1 ;i<=n ;i++) {
            if (tmp) {
                tmp /= q;
                maxx += 1;
                thi *= q;
            }
            else {
                break;
            }
        }
        dfs(n ,maxx+2 ,1 ,1);
        printf("\n");
    }


    return 0;
}