InTheBloodHorse

每日一题(16) codeforces 1041B

字数统计: 138阅读时长: 1 min
2018/09/27 Share

题目地址
题意:
问 在[1,x],[1,y],比例 等于 a:b的个数
思路:
把a:b的比例约分,这样就能保证最小,其实就是除以 gcd(a,b)。
然后除以比例就好了,找出最小的。
AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) {
return b == 0 ? a : gcd(b, a % b);
}
int main()
{
long long x,y,a,b;
cin >> x >> y >> a >> b;
long long div = gcd(a,b);
a/=div;
b/=div;
cout << min(x/a,y/b) << endl;
}

CATALOG