Multiplying Digits Gym - 101490H

妖狐艹你老母 2022-06-08 04:28 64阅读 0赞

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