# A1009 Product of Polynomials (25 分)

## 题目内容

This time, you are supposed to find A×B where A and B are two polynomials.

### Input Specification:

Each input file contains one test case. Each case occupies 2 lines, and each line contains the information of a polynomial:

K N1 aN1 N2 aN2... NKaNK

where K is the number of nonzero terms in the polynomial, Niand aNi(i=1,2,?,K) are the exponents and coefficients, respectively. It is given that 1≤K≤10，0≤NK<?<N2<N1≤1000.

### Output Specification:

For each test case you should output the product of A and B in one line, with the same format as the input. Notice that there must be NO extra space at the end of each line. Please be accurate up to 1 decimal place.

2 1 2.4 0 3.2

2 2 1.5 1 0.5

### Sample Output:

3 3 3.6 2 6.0 1 1.6

### 单词

#### product

n. 产品；结果；[数] 乘积；作品

## 具体代码

```#include<stdio.h>
#include<stdlib.h>

double p1[1001];
double p2[1001];
double res[2002];
int N, M;
int main(void)
{
scanf("%d", &N);
for (int i = 0; i < N; i++)
{
int e;
double c;
scanf("%d %lf", &e, &c);
p1[e] = c;
}
scanf("%d", &M);
for (int i = 0; i < M; i++)
{
int e;
double c;
scanf("%d %lf", &e, &c);
p2[e] = c;
}
for (int i = 0; i < 1001; i++)
{
if (p1[i] != 0)
for (int j = 0; j < 1001; j++)
if (p2[j] != 0)
res[i + j] += p1[i] * p2[j];
}
int num = 0;
for (int i = 0; i < 2002; i++)
{
if (res[i] != 0)
num++;
}
printf("%d", num);
for (int i = 2001; i >= 0; i--)
{
if (res[i] != 0)
printf(" %d %0.1f", i, res[i]);
}
system("pause");
}
```

## 题目内容

Given a pair of positive integers, for example, 6 and 110, can this equation 6 = 110 be true? The answer is yes, if 6 is a decimal number and 110 is a binary number.

Now for any pair of positive integers N1 and N?2, your task is to find the radix of one number while that of the other is given.

### Input Specification:

Each input file contains one test case. Each case occupies a line which contains 4 positive integers:

Here N1 and N2 each has no more than 10 digits. A digit is less than its radix and is chosen from the set { 0-9, a-z } where 0-9 represent the decimal numbers 0-9, and a-z represent the decimal numbers 10-35. The last number radix is the radix of N1 if tag is 1, or of N2 if tag is 2.

### Output Specification:

For each test case, print in one line the radix of the other number so that the equation N1 = N2 is true. If the equation is impossible, print Impossible. If the solution is not unique, output the smallest possible radix.

6 110 1 10

2

n. 根；[数] 基数

n. 小数

## 题目分析

```
int sum=0;
while(*p != ‘\0‘)
{
int n = convert(*p);
sum = sum * radix + n;
p++;
}
```

## 具体代码

```#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXSIZE 11

char s1[MAXSIZE];
char s2[MAXSIZE];
int tag;
long long result;

int convert(char a)
{
if (a >= ‘0‘&&a <= ‘9‘)
return a - ‘0‘;
else
return a - ‘a‘ + 10;
}

long long count_num(char *s, long long radix)
{
char *p = s;
long long sum = 0;
while(*p != ‘\0‘)
{
int n = convert(*p);
sum = sum * radix + n;
p++;
}
return sum;
}

{
long long max = 0;
char *p = s;
while(*p!=‘\0‘)
{
int f = convert(*p);
if (f > max)
max = f;
p++;
}
return max + 1;
}

long long binary_search(long long result,char *s,long long rmin,long long rmax)
{
while (rmin <= rmax)
{
long long mid = rmin+(rmax-rmin)/2;
long long n = count_num(s, mid);
if (n > result || n < 0 )
rmax = mid - 1;
else if (n < result)
rmin = mid + 1;
else
return mid;
}
return -1;
}

int main(void)
{
char c1[MAXSIZE];
char c2[MAXSIZE];
scanf("%s %s %d %lld", c1, c2, &tag, &radix);
if (tag == 1)
{
strcpy(s1, c1);
strcpy(s2, c2);
}
else
{
strcpy(s2, c1);
strcpy(s1, c2);
}
long long rmax;
if(result != 0)
rmax = result + 1;
else
rmax = 2;
long long r = binary_search(result, s2, rmin, rmax);
if (r == -1)
printf("Impossible");
else
printf("%lld", r);
system("pause");
}
```