Multiplying Digits Gym - 101490H

妖狐艹你老母 2022-06-08 04:28 136阅读 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;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，136人围观）

还没有评论，来说两句吧...

相关阅读

相关 gym224647B

gym224647B 题意： > 在二维平面中·选出一个面积最小的三角形，输出这个三角形面积的两倍。解法： > 首先，最优解一定在相邻最近的三个点...

青旅半醒/ 2024年04月20日 10:31/ 0 赞/ 78 阅读

相关 Gym - 100199C

Gym - 100199C 题意： > 其实这么长的英文题面就是想告诉我们这个题是丢手绢。解法： > 找到与 $ N $ 互质的最大整数 $ K ...

╰+哭是因爲堅強的太久メ/ 2024年04月20日 10:29/ 0 赞/ 76 阅读

相关 Digits

\\(Digits\\) ![m6C1AO.png][] 这道题目比较简单，首先先打出来暴力，然后一看\\(b\\)的范围，瞬间想到快速幂。快速幂的精髓是什么？

偏执的太偏执、/ 2023年06月01日 15:00/ 0 赞/ 28 阅读

相关 H - Digit Counting

Trung is bored with his mathematics homeworks. He takes a piece of chalk and starts writ

￡神魔★判官ぃ/ 2022年10月01日 04:51/ 0 赞/ 3 阅读

相关 GYM 100685 K

乱搞题统计每一个不是magic word的单词，然后每个make\_pair 然后按照公式计算答案。因为这里是乱序的统计make\_pair的情况，所以如果相邻

比眉伴天荒/ 2022年08月04日 14:41/ 0 赞/ 127 阅读

相关 leetcode-258.add digits/Digital root

leetcode-258.Add Digits Given a non-negative integer num, repeatedly add all its digi

痛定思痛。/ 2022年07月28日 00:13/ 0 赞/ 186 阅读

相关 Multiplying Digits Gym - 101490H

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

妖狐艹你老母/ 2022年06月08日 04:28/ 0 赞/ 137 阅读

相关 Gym - 101522H Hit!

H. Hit! time limit per test 1.0 s memory limit per test 256 MB input standard inpu

港控/mmm°/ 2022年05月29日 05:46/ 0 赞/ 151 阅读

相关 Gym - 101201H

![70][] 题意：有k个区间，用他们填满1~n，不允许重叠，问留下的空隙最少是多少思路：可以从两方面考虑，第一个是正面考虑，转移方程dp\[i\]=min(dp\[j

野性酷女/ 2022年05月14日 12:51/ 0 赞/ 109 阅读

相关 gym101915e

include <bits/stdc++.h> define N 10 using namespace std; int a

快来打我*/ 2022年04月24日 11:16/ 0 赞/ 114 阅读