hduoj 6668 Polynomial - 百度之星 2019

目录

1. 题目描述
   1. Problem Description
   2. Input
   3. Output
   4. Sample Input
   5. Sample Output
   6. 样例描述
2. 解答

题目描述

Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 32768/32768 K (Java/Others)

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) = 2x$
$g(x) = 1$
$f(x) = 1$
$g(x) = 2x$
$f(x) = 4x + 2$
$g(x) = 2x + 1$

解答

比较两个多项式最高项系数即可，分情况：

1. 如果两个多项式最高项的次数不等：

   1. 如果 f(x) 的高：

      输出： 1/0

   2. 如果 g(x) 的高：

      输出： 0/1

2. 如果两多项式的最高次项相等：

   输出两个最高项系数约分以后的结果。（需要求两数最大公约数）

代码

#include <cstdio>


int a[1003], b[1003];

int gcm(int x,int y) {
    int maxv = x, minv = y, tmp;
    if(x < y) {
        maxv = y;
        minv = x;
    }
    tmp = maxv % minv;
    while(tmp != 0) {
        maxv = minv;
        minv = tmp;
        tmp = maxv % minv;
    }
    return minv;
}


int main() {
    int T;
    scanf("%d", &T);
    while (T --) {
        int n;
        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){
                if (b[i] != 0) {
                    printf("0/1\n"); break;
                }
                
            }
            else if (b[i] == 0) {
                printf("1/0\n"); break;
            }
            else {
                int c = gcm(a[i], b[i]);
                printf("%d/%d\n", a[i] / c, b[i] / c); break;
            }
        }
    }
}