문제
“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;
}
'백준 알고리즘' 카테고리의 다른 글
<백준 알고리즘> 16395번: 파스칼의 삼각형 (0) | 2020.09.27 |
---|---|
<백준 알고리즘> 16199번: 나이 계산하기 (0) | 2020.09.27 |
<백준 알고리즘> 15989번: 1, 2, 3 더하기 4 (0) | 2020.09.27 |
<백준 알고리즘> 1408번: 24 (0) | 2020.09.27 |
<백준 알고리즘> 16394번: 홍익대학교 (0) | 2020.09.26 |