CCF NOI1056 表达式

时间限制: 1000 ms 空间限制: 262144 KB

题目描述

表达式6×9=42对于十进制来说是错误的，但是对于十三进制来说是正确的。即6(13)×9(13)=42(13)，而42(13)=4×131+2×130=54(10)。你的任务是写一段程序读入3个整数p、q和r，然后确定一个进制B(2≤B≤16)使得p×q=r。如果B有很多选择，输出最小的一个。例如：p=11,q=11,r=121。则有11(3) ×11(3)=121(3)，11(10) ×11(10)=121(10)。这种情况下，输出3。如果没有合适的进制，则输出0。

输入

一行，3个B进制的正整数p、q、r（数位≤7）。

输出

使得p×q=r成立的最小进制B，如果没有合适的进制，则输出0。

样例输入

6 9 42
样例输出

数据范围限制

提示

问题分析

这是一个进制问题，穷举法一个一个试。

开始时从16进制开始往小试，只得了80分，题意要求是如果两种进制都符合，输出小的进制。

对于B进制，那么其数字只能小于B，例如8进制使用的数字是0-7。

程序说明

开始时不论是什么进制，先都按10进制输入，然后再用函数convert()进行转换。

要点详解

使用宏定义可以使得代码可阅读性增强。
C语言程序，功能要尽量封装到函数中。

参考链接：（略）。

100分通过的C语言程序：

#include <stdio.h>

const int BASE10 = 10;

long convert(long v, int base)
{
    long ans, weight;
    int digit;

    ans = 0;
    weight = 1;
    while(v) {
        digit = v % BASE10;
        v /= BASE10;
        if(digit >= base) {
            ans = -1;
            break;
        }

        ans += weight * digit;

        weight *= base;
    }

    return ans;
}

int main(void)
{
    long p, q, r;
    long p2, q2, r2;
    int ans, i;

    scanf("%ld%ld%ld", &p, &q, &r);
    ans = 0;
    for(i=2; i<16; i++) {
        p2 = convert(p, i);
        if(p2 < 0) {
            ans = 0;
            continue;
        }
        q2 = convert(q, i);
        if(q2 < 0) {
            ans = 0;
            continue;
        }
        r2 = convert(r, i);
        if(r2 < 0) {
            ans = 0;
            continue;
        }

        if(p2 * q2 == r2) {
            ans = i;
            break;
        }
    }

    printf("%d
", ans);

    return 0;
}