洛谷 P2118 比例简化（枚举）

嗯...

题目链接：https://www.luogu.org/problem/P2118

这道题的出题人很善良，l的范围不是很大，所以我们可以逐一枚举。

本题主要思想就是把所有的比例都转换为乘积的形式。

因为 i / j >= A / B

所以 i * B >= j * A

因为要找差距最小

所以 i / j < C / D

所以 i * D < j * C

综上所述，查找到的 i，j 应当满足 i * B >= j * A && i * D < j * C && i，j 的最小公因数为1。

AC代码：

 #include<cstdio>

 #include<iostream>

 using namespace std;

 int a, b, c, d = , l;

 inline int gcd(int x, int y){

     if(y == ) return x;

     return gcd(y, x % y);

 }

 int main(){

     scanf("%d%d%d", &a, &b, &l);

     c = l;

     for(int i = ; i <= l; i++){

         for(int j = ; j <= l; j++){

             if(gcd(i, j) ==  && i * b >= j * a && i * d < j * c){

                 c = i;

                 d = j;

             }

         }

     }

     printf("%d %d", c, d);

     return ;

 }

AC代码

巴特西

洛谷 P2118 比例简化（枚举）

最新文章

热门文章