ACM: FZU 2102 Solve equation - 手速题

时间：2022-07-18 19:46:40
 FZU 2102   Solve equation

Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u

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.

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.

Output

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

Sample Input

3

2bc 33f 16

123 100 10

1 1 2

Sample Output

(0,700)

(1,23)

(1,0)

任意进制转化问题，然后满足 A = k * B + d ; 最大，直接就是 k = A / B , d = A % B ;

AC代码：

#include"algorithm"

#include"iostream"

#include"cstring"

#include"cstdlib"

#include"cstdio"

#include"string"

#include"vector"

#include"stack"

#include"queue"

#include"cmath"

#include"map"

using namespace std;

typedef long long LL ;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define FK(x) cout<<"["<<x<<"]\n"

#define memset(x,y) memset(x,y,sizeof(x))

#define memcpy(x,y) memcpy(x,y,sizeof(x))

#define bigfor(T)  for(int qq=1;qq<= T ;qq++)

const int MX=50;

int main() {

	int T;

	LL c;

	char a[50],b[50];

	scanf("%d",&T);

	bigfor(T) {

		scanf("%s %s %I64d",a,b,&c);

		int la=strlen(a);

		int lb=strlen(b);

		LL aa=0,bb=0;

		LL m=1;

		for(int i=la-1; i>=0; i--) {

			if(a[i]<='9'&&a[i]>='0')aa+=(a[i]-'0')*m;

			if(a[i]<='f'&&a[i]>='a')aa+=(a[i]-'a'+10)*m;

			m*=c;

		}

		m=1;

		for(int i=lb-1; i>=0; i--) {

			if(b[i]<='9'&&b[i]>='0')bb+=(b[i]-'0')*m;

			if(b[i]<='f'&&b[i]>='a')bb+=(b[i]-'a'+10)*m;

			m*=c;

		}

		LL ans1,ans2;

		ans1=aa/bb;

		ans2=aa%bb;

		printf("(%I64d,%I64d)\n",ans1,ans2);

	}

	return 0;

}

　　









相关文章