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

Hint

這些多項式分別為
f(x) = 2x
g(x) = 1
f(x) = 1
g(x) = 2x
f(x) = 4x + 2
g(x) = 2x + 1

思路：首先記錄?f(x)、g(x) 兩個式子的系數不為 0 的最高次項，然后比較兩者最高次項位置的關系，只有相等時求 gcd 即可

Source Program

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #include<bitset> #define EPS 1e-9 #define PI acos(-1.0) #define INF 0x3f3f3f3f #define LL long long #define Pair pair<int,int> const int MOD = 1E9+7; const int N = 1000+5; const int dx[] = {0,0,-1,1,-1,-1,1,1}; const int dy[] = {-1,1,0,0,-1,1,-1,1}; using namespace std;int a[N]; int b[N]; int main(){int t;scanf("%d",&t);while(t--){int n;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=1;i<=n;i++)scanf("%d",&b[i]);int up,upPos;for(int i=n;i>=1;i--){if(a[i]!=0){upPos=i;up=a[i];break;}}int down,downPos;for(int i=n;i>=1;i--){if(b[i]!=0){downPos=i;down=b[i];break;}}if(upPos>downPos)printf("1/0\n");else if(upPos<downPos)printf("0/1\n");else{int gcd=__gcd(up,down);printf("%d/%d\n",up/gcd,down/gcd);}} }

?

總結

以上是生活随笔為你收集整理的Polynomial（HDU-6668）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。