欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  科技

PAT 1010 Radix (25分)

程序员文章站 2022-07-08 17:23:07
题目链接:点击这里题意:现给定两个正整数 N1,N2N_1,\ N_2N1​,N2​,并给出其中一个数的进制,请你求出另一个数在什么进制下,能使得两数相等。技巧:如果 tag 等于 2,就把两数交换,可以减少一半的对称代码。交换之后,N1N_1N1​ 是已知进制的,N2N_2N2​ 是未知进制的。但是题目中没有指明输入的 radix 的数据范围,所以 N1N_1N1​ 也可能是爆 long long 的,为了使题目能够顺利做下去,这里默认 N1N_1N1​ 最大为 (zzzzz...

题目链接:点击这里

题意:现给定两个正整数 N 1 ,   N 2 N_1,\ N_2 N1, N2,并给出其中一个数的进制,请你求出另一个数在什么进制下,能使得两数相等。

技巧:如果 tag 等于 2,就把两数交换,可以减少一半的对称代码。

交换之后, N 1 N_1 N1 是已知进制的, N 2 N_2 N2 是未知进制的。但是题目中没有指明输入的 radix 的数据范围,所以 N 1 N_1 N1 也可能是爆 long long 的,为了使题目能够顺利做下去,这里默认 N 1 N_1 N1 最大为 ( z z z z z z z z z z ) 36 (zzzzzzzzzz)_{36} (zzzzzzzzzz)36,即 N 1 N_1 N1 的十进制数最大为 3 6 10 36^{10} 3610,故用 long long 即可。

对于未知进制的 N 2 N_2 N2,它的进制可能会非常大,最大进制不仅仅是 36 36 36 这么简单。

如果暴力枚举 N 2 N_2 N2 的进制,会超时。

我们知道,进制越大, N 2 N_2 N2 所代表的十进制数就越大,利用这个单调性,我们可以二分枚举出 N 2 N_2 N2 的进制。二分的左边界 l l l 等于 N 2 N_2 N2 中所有字符的最大值加 1 1 1,二分的右边界等于 N 1 N_1 N1 和 36 两者中的最大值。

AC代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;
typedef long long ll;

char a[15], b[15];
int tag, radix;

int get(char x)
{
    if(x >= '0' && x <= '9')  return x - '0';
    else    return x - 'a' + 10;
}

ll calc(ll r)
{
    ll res = 0;
    for(int i = 0; b[i]; i++)
    {
        if((double)res * r + get(b[i]) > 1e16) return 1e16;
        res = res * r + get(b[i]);
    }
    return res;
}

int main()
{
    scanf("%s%s%d%d", a, b, &tag, &radix);
    
    if(tag == 2)    swap(a, b); // 交换,以减少对称的代码量
    
    ll n1 = 0;
    for(int i = 0; a[i]; i++)   n1 = n1 * radix + get(a[i]);
    
    int maxb = -1;
    for(int i = 0; b[i]; i++)   maxb = max(maxb, get(b[i]));
    
    ll l = maxb + 1, r = max(n1, 36ll);
    
    while(l < r)                // 找到第一个大于等于n1所对应的进制
    {
        ll mid = l + r >> 1;
        if(calc(mid) >= n1) r = mid;
        else l = mid + 1;
    }

    if(calc(r) != n1)   puts("Impossible");
    else    printf("%lld\n", r);
    
    return 0;
}

微信公众号《算法竞赛求职》,致力于详细讲解竞赛和求职所涉及到的算法原理和模板。欢迎关注,一起交流进步!

本文地址:https://blog.csdn.net/qq_42815188/article/details/109000006

相关标签: PAT