Strange Optimization(扩展欧几里得)

Strange Optimization
Accepted : 67		Submit : 289
Time Limit : 1000 MS		Memory Limit : 65536 KB

Strange Optimization

Bobo is facing a strange optimization problem. Given n,m , he is going to find a real number α such that f(12+α) is maximized, where f(t)=mini,j∈Z|in−jm+t| . Help him!

Note: It can be proved that the result is always rational.

Input

The input contains zero or more test cases and is terminated by end-of-file.

Each test case contains two integers n,m .

• 1≤n,m≤109
• The number of tests cases does not exceed 10⁴ .

Output

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

Sample Input

1 1
1 2

Sample Output

1/2
1/4

Note

For the first sample, α=0 maximizes the function

//题意还是很好懂的，只要明白扩展欧几里得原理，这题很简单，i/n - j/m 可以化为 ( mi - nj ) / ( n * m )

因为 i，j 为整数所以等于  k*gcd(n,m)/(n*m)

所以 f(t)的最大值为 1 / ( Lcm(n,m)*2 )

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL long long

LL gcd(LL a,LL b)
{
    return b==0?a:gcd(b,a%b);
}

int main()
{
    LL n,m;
    while (scanf("%I64d%I64d",&n,&m)!=EOF)
    {
        LL p = gcd(n,m);
        LL q = n*m*2;
        LL yue = gcd(p,q);
        printf("%I64d/%I64d
",p/yue,q/yue);
    }
    return 0;
}