<백준 알고리즘> 3232번: Multiply

문제

“6 × 9 = 42” is not true for base 10, but is true for base 13. That is, 6(13) × 9(13) = 42(13) because 42(13) = 4 × 131 + 2 × 130 = 54(10).

You are to write a program which inputs three integers p, q, and r and determines the base B (2 ≤ B ≤ 16) for which p × q = r. If there are many candidates for B, output the smallest one. For example, let p = 11, q = 11, and r = 121. Then we have 11(3) × 11(3) = 121(3) because 11(3) = 1 × 31 + 1 × 30 = 4(10) and 121(3) = 1 × 32 + 2 × 31+ 1 × 30 = 16(10). For another base such as 10, we also have 11(10) × 11(10) = 121(10). In this case, your program should output 3 which is the smallest base. If there is no candidate for B, output 0.

입력

The input consists of T test cases. The number of test cases (T ) is given in the first line of the input file. Each test case consists of three integers p, q, and r in a line. All digits of p, q, and r are numeric digits and 1 ≤ p, q, r ≤ 1,000,000.

출력

Print exactly one line for each test case. The line should contain one integer which is the smallest base for which p × q = r. If there is no such base, your program should output 0.

예제 입력 1

3 6 9 42 11 11 121 2 2 2

예제 출력 1

13 3 0

---

Solution

#include<stdio.h>
#include<math.h>
#include<stdbool.h>

int maxdigit(int p,int q,int r)
{
	int max=0;

	while(p>0)
	{
		max=p%10>max?p%10:max;
		p/=10;
	}
	while(q>0)
	{
		max=q%10>max?q%10:max;
		q/=10;
	}
	while(r>0)
	{
		max=r%10>max?r%10:max;
		r/=10;
	}

	return max;
}

int todecimal(int x,int n)
{
	int decimal=0;

	for(int i=0;x>0;i++)
	{
		decimal+=(x%10)*(int)pow((double)n,(double)i);
		x/=10;
	}

	return decimal;
}

int main(void)
{
	int T;

	scanf("%d", &T);

	for(int t=0;t<T;t++)
	{
		int p, q, r;
		bool solved=false;

		scanf("%d %d %d", &p, &q, &r);

		for(int n=maxdigit(p,q,r)+1;n<=16;n++)
			if(todecimal(p,n)*todecimal(q,n)==todecimal(r,n))
			{
				printf("%d\n", n);
				solved=true;
				break;
			}

		if(!solved)
			printf("0\n");
	}

	return 0;
}