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/2n*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;
}
推荐阅读
-
Strange Optimization
-
MySQL查询优化之四-引擎条件下推优化优化(Engine Condition Pushdown Optimization)
-
卷积神经网络 + 机器视觉: L3_Loss Functions and Optimization (斯坦福CS231n)
-
HPM Note5, Query Performance Optimization 博客分类: Database performanceMySQLSQL Serverthreadmemcached
-
HPM Note5, Query Performance Optimization 博客分类: Database performanceMySQLSQL Serverthreadmemcached
-
Windows 10 VDI optimization
-
webpack源码解析七(optimization)
-
Heat Map and Automatic Data Optimization : part-2
-
Heat Map and Automatic Data Optimization : part-2
-
Priority queue optimization for filesort is now visible in M_MySQL