fuz-2102

Bertha 。 2022-05-27 03:15 143阅读 0赞

## Problem Description ##

You are given two positive integers A and B in Base C. For the equation:

A=k\*B+d

We know there always existing many non-negative pairs (k, d) that satisfy the equation above. Now in this problem, we want to maximize k.

For example, A="123" and B="100", C=10. So both A and B are in Base 10. Then we have:

(1) A=0\*B+123

(2) A=1\*B+23

As we want to maximize k, we finally get one solution: (1, 23)

The range of C is between 2 and 16, and we use 'a', 'b', 'c', 'd', 'e', 'f' to represent 10, 11, 12, 13, 14, 15, respectively.

## ![prodesc.gif][] Input ##

The first line of the input contains an integer T (T≤10), indicating the number of test cases.

Then T cases, for any case, only 3 positive integers A, B and C (2≤C≤16) in a single line. You can assume that in Base 10, both A and B is less than 2^31.

## ![prodesc.gif][] Output ##

For each test case, output the solution “(k,d)” to the equation in Base 10.

## ![prodesc.gif][] Sample Input ##

32bc 33f 16123 100 101 1 2

## ![prodesc.gif][] Sample Output ##

(0,700)(1,23)(1,0)

## ![prodesc.gif][] Source ##

“高教社杯”第三届福建省大学生程序设计竞赛

题目大意：给你两个字符串和一个数字，数字表示是字符串的进制数，问如何计算使得A=k\*B+d中k的值最大；

思路：由题意可知应先将AB两数所表示的十进制数算出来，若k最大则k=a/b;

代码：

#include<queue>
    #include<cmath>
    #include<cstdio>
    #include<cstring>
    #include<cstdlib>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    char s1[100],s2[100];
    int zhuanhuan(char b[],int c)
    {
        int i,l,ans=0;
        for(i=0;i<strlen(b);i++)
        {
            int tem;
            if(b[i]>='0'&&b[i]<='9')
                tem=b[i]-'0';
            else
                tem=b[i]-'a'+10;
            ans=ans*c+tem;
        }
        return ans;
    }
    int main()
    {
        int test;
        scanf("%d",&test);
        getchar();
        while(test--)
        {
            int c;
            scanf("%s%s%d",s1,s2,&c);
            int a=zhuanhuan(s1,c);
            int b=zhuanhuan(s2,c);
            int ans=a/b;
            printf("(%d,%d)\n",ans,a-ans*b);
        }
        return 0;
    }

[prodesc.gif]: http://acm.fzu.edu.cn/image/prodesc.gif