2019牛客多校第一场 J-Fraction Comparision

it2022-05-05  123

题目链接:https://ac.nowcoder.com/acm/contest/881/J

分析:

比较x/a与y/b的大小,x, y的范围是1e18,a, b的范围是1e9,用一般的通分变成xb与ya这种交叉相乘的形式进行比较会爆long long,当然比较取巧的做法是用java大数,但正规做法是把这两个分数给他分成整数部分和小数部分,而小数部分又可以用分数来表示,比如x/a,其整数部分是x//a,即x整除a,然后小数部分写成分数就是(x mod a)/a,y/b同理,然后整数部分若不相等则可以直接判断大小,若相等就再看小数部分,这里小数部分的分数形式就可以用交叉相乘比较而不会爆long long了。

AC代码:

#include <algorithm> #include <cctype> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> #include <map> #include <queue> #include <stack> #include <string> #include <set> #include <vector> #include <bitset> using namespace std; typedef long long ll; const int INF = 0x3f3f3f3f; const double PI = acos(-1.0); const int MAXN = 3e5+10; int main() { ll x, y, a, b; while(~scanf("%lld%lld%lld%lld", &x, &a, &y, &b)) { ll ia = x/a, ib = y/b; if(ia > ib) printf(">"); else if(ia < ib) printf("<"); else { ll da = x%a, db = y%b; da *= b, db *= a; if(da > db) printf(">"); else if(da == db) printf("="); else printf("<"); } puts(""); } return 0; }

最新回复(0)