2019 年百度之星·程序设计大赛 初赛 1001 Polynomial

1001 Polynomial （基础数学）

Problem Description

度度熊最近学习了多项式和极限的概念。现在他有两个多项式 f(x) 和 g(x)，他想知道当 x 趋近无限大的时候，f(x)/g(x) 收敛于多少。

Input

第一行一个整数 T (1≤T≤100) 表示数据组数。对于每组数据，第一行一个整数 n (1≤n≤1,000)，n−1 表示多项式 f 和 g 可能的最高项的次数（最高项系数不一定非0）。接下来一行 n 个数表示多项式 f，第 i 个整数 fi (0≤fi≤1,000,000) 表示次数为 i−1 次的项的系数。接下来一行 n 个数表示多项式 g，第 i 个整数 gi (0≤gi≤1,000,000)表示次数为 i−1 次的项的系数。数据保证多项式 f 和 g 的系数中至少有一项非0。

Output

对于每组数据，输出一个最简分数 a/b（a 和 b 的最大公约数为1）表示答案。如果不收敛，输出 1/0。

Sample Input

3

2

0 2

1 0

2

1 0

0 2

3

2 4 0

1 2 0

Sample Output

1/0

0/1

2/1

样例描述

这些多项式分别为

f(x)=2xf(x) = 2xf(x)=2x

g(x)=1g(x) = 1g(x)=1

f(x)=1f(x) = 1f(x)=1

g(x)=2xg(x) = 2xg(x)=2x

f(x)=4x+2f(x) = 4x + 2f(x)=4x+2

g(x)=2x+1g(x) = 2x + 1g(x)=2x+1

题意分析：

给出两个多项式各项的系数，求f(x)/g(x)趋近多少。

解题思路：

当两者的最高项都不为0时，趋近与两者之比；

当f(x)最高项为0时趋近0，即0/1，

当g(x)最高项为0时趋近1，即1/0。

此最高项是两者中次数大的项， 注意化简为最简分数。

代码：

#include <stdio.h>
#include <algorithm>
#define N 1020
using namespace std;
int a[N], b[N];
int main() {
int t, n;
scanf("%d", &t);
while(t--)
{
scanf("%d", &n);
for(int i=0; i<n; i++)
scanf("%d", &a[i]);
for(int i=0; i<n; i++)
scanf("%d", &b[i]);
for(int i=n-1; i>=0; i--)
{
if(a[i]==0 && b[i]==0)
continue;
if(a[i]==0)
{
printf("0/1\n");
break;
}

else if(b[i]==0) {
printf("1/0\n");
break;
}
else 
{
int c=__gcd(a[i], b[i]);
printf("%d/%d\n", a[i]/c, b[i]/c);
break;
}
}
}
return 0;
}