题目解析
给定多项式a与多项式b，求 的商和余数
解题思路
首先需要先知道多项式除法的过程是怎么样子的，然后根据多项式除法的过程模拟即可
根据题目意思，所有指数是降序给出的，所以存储第一个质数，找出多项式中最大的项。
然后模拟多项式除法的过程即可。
- 得到商
- 消去相等项
- 更新其余项
- 去除商中的零项
- 重复执行以上操作即可
注： 题目中系数是保留一位小数。如果该系数四舍五入后无法保留到达0.1的指数，则当该项为零项。
代码
import java.io.*;
import java.math.*;
import java.util.*;
public class Main
{
static int N = (int) 1e4 + 10;
// 下标为质数，下标相对应的数为系数
static double a[] = new double[N]; // 多项式a
static double b[] = new double[N]; // 多项式b
static double c[] = new double[N]; // 多项式a / 多项式b 的结果
// 四舍五入是否能到达0.1
static boolean check(double x)
{
return Math.abs(x) + 0.05 >= 0.1;
}
static void print(double shu[], int n)
{
// 查看多项式中，有多少个非零项
int cnt = 0;
for (int i = 0; i <= n; i++)
{
if (check(shu[i])) cnt++;
}
// 输出项数
out.print(cnt);
// 零多项式
if (cnt == 0) out.print(" 0 0.0");
// 递减输出多项式中的非零项
for (int i = n; i >= 0; i--)
{
if (check(shu[i])) out.printf(" %d %.1f", i, shu[i]);
}
}
public static void main(String[] args) throws IOException
{
int n = ini();
int mx1 = 0; // 第一个多项式中的最高指数
int mx2 = 0; // 第二个多项式中的最高质数
for (int i = 1; i <= n; i++)
{
int e = ini(); // 输入质数
a[e] = ind(); // 输入相对应的系数
if (i == 1) mx1 = e; // 如果是第一项，则最高质数就是该质数
}
n = ini();
for (int i = 1; i <= n; i++)
{
int e = ini(); // 输入质数
b[e] = ind(); // 输入相对应的系数
if (i == 1) mx2 = e; // 如果是第一项，则最高质数就是该质数
}
int t = mx1 - mx2; // 多项式c中第一项的指数
while (mx1 >= mx2)
{
double p = a[mx1] / b[mx2]; // 获得商
c[mx1 - mx2] = p; // mx1-mx2 项的系数
for (int i = mx1, j = mx2; i >= 0 && j >= 0; i--, j--) a[i] -= b[j] * p; // 指数相同的对应位置的系数相减
while (mx1 >= mx2 && !check(a[mx1])) mx1--; // 找到非零项
}
print(c, t); // 输出商
out.println();
print(a, mx1); // 输出余数
out.flush();
out.close();
}
static StreamTokenizer sc = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static PrintWriter out = new PrintWriter(System.out);
static int ini() throws IOException
{
sc.nextToken();
return (int) sc.nval;
}
static double ind() throws IOException
{
sc.nextToken();
return sc.nval;
}
}