首页 > 代码库 > HTPJ 1268 GCD
HTPJ 1268 GCD
链接:
http://202.197.224.59/OnlineJudge2/index.php/Problem/read/id/1268
题意:
给出n,m,定义f(t)=min |i/n−j/m+t| (i,j∈Z) 。求f(t)的最大值
题解:
i/n-j/m = (i*m - j*n) / (n*m),分子 = k*gcd(n,m)。令d = gcd(n,m),
所以就是求 min |k*d / (n*m) +t| 的最大值,所以相邻两个结果之间的距离为d / (n*m),
要想让值最大,就是当t为中点,此时最小值为d / (2*n*m), ans = 1 / (2*n*m / gcd(n,m))。
代码:
31 ll gcd (ll a, ll b) {32 return b == 0 ? a : gcd (b, a % b);33 }34 35 int main() {36 ll n, m;37 while (cin >> n >> m)38 cout << "1/" << 2 * n*m / gcd (n, m) << endl;39 return 0;40 }
HTPJ 1268 GCD
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。