Multiplying Digits Gym - 101490H-蒲公英云

Multiplying Digits Gym - 101490H

Think:
1知识点：map + 思维 + 剪枝
2题意：y为x在b进制下的各位数的乘积，输入b y，求满足的最小x
3方法：
（1）：先得到y小于b的因子，然后在因子乘积等于y的约束下组合因子，得到最小的x

以下为Accepted代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL Inf = 0x7fffffffffffffff;
LL tp, link[11400];
map<LL, LL> mp;
map<LL, LL> :: reverse_iterator it;
int main(){
    LL b, n, tmp, i, u, v, x, y, mo;
    while(~scanf("%lld %lld", &b, &n)){
        if(n == 1){
   /*n = 1的特殊情况*/
            printf("1\n");
            continue;
        }
        tp = 0, tmp = n;
        for(i = 2; i < b; i++){
            if(n%i == 0) link[tp++] = i;
            while(tmp%i == 0){
                tmp /= i;
            }
        }
        if(tmp != 1) {
            printf("impossible\n");
            continue;
        }
        mp.clear();
        mp[n] = 0;
        for(it = mp.rbegin(); it != mp.rend(); it++){
            u = it->first, v = it->second;
            mo = v%b;
            for(i = tp-1; i>= 0; i--){
                if(link[i] < mo) break;/*最优解的组成为非严格递增，所以若后一位小于前一位，则一定不是整体最优解*/
                if(u%link[i]) continue;
                if((Inf-link[i])/b < v) continue;/*防止爆long long*/
                x = u/link[i], y = v*b + link[i];
                if((!mp[x]) || mp[x] > y) mp[x] = y;
            }
        }
        printf("%lld\n", mp[1]);
    }
    return 0;
}