P5623 [Celeste-A] Sever the Skyline 题解

· · 题解

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;
}