Strange Optimization

NC52868. Strange Optimization

描述

Bobo is facing a strange optimization problem.
Given n, m, he is going to find a real number $\alpha$ such that $f(\frac{1}{2} + \alpha)$ is maximized, where $f(t) = \min_{i, j \in \mathbb{Z}} |\frac{i}{n} - \frac{j}{m} + t|$ .
Help him!
Note: It can be proved that the result is always rational.

输入描述

The input contains zero or more test cases and is terminated by end-of-file. 
Each test case contains two integers n, m.
* 
* The number of tests cases does not exceed .

输出描述

For each case, output a fraction p/q which denotes the result.

示例1

输入:

1 1
1 2

输出:

1/2
1/4

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 36ms, 内存消耗: 608K, 提交时间: 2019-10-04 23:20:14

#include<bits/stdc++.h>
using namespace std;
int main(){
    long long n,m;
    while(cin>>n>>m){
        cout<<"1/"<<2*n/__gcd(n,m)*m<<endl;
    }
}

C++11(clang++ 3.9) 解法, 执行用时: 34ms, 内存消耗: 600K, 提交时间: 2019-10-04 17:18:33

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
	ll n,m; while(cin>>n>>m) cout<<"1/"<<2*n/__gcd(n,m)*m<<endl;
}

上一题

下一题

详情