欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Strange Optimization

程序员文章站 2024-03-19 09:25:46
...

题目意思是要求在t固定的情况下,i,j任意取值,求得f(t)的所有最小值中的最大值。
对于i/n-j/m而言,根据拓展欧几里得的有解的条件,那么它可以表示gcd(n,m)/(nm)的任意倍数,那么当t是固定的时,t到和它最近的两个gcd(n,m)/(nm)的倍数之间的距离中的最小值必然小于等于gcd(n,m)/2*(nm),所以,要求最大的f(t),那么其值应该为gcd(n,m)/2(nm) ,若分子为1,则为
1/2
n*m/gcd(n,m)。为了防止溢出,先除 后乘。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m;
int main()
{
    while(scanf("%lld%lld",&n,&m)!=EOF)
    {
        printf("1/%lld\n",2*n/__gcd(n,m)*m);
    }
    return 0;
}