Informatics Olympiad All-in-One 1966: [14NOIP Popularization Group] Scale Simplification | Luogu P2118 [NOIP2014 Popularization Group] Scale Simplification

【题目链接】

ybt 1966：【14NOIP普及组】比例简化
洛谷 P2118 [NOIP2014 普及组] 比例简化

【题目考点】

1. 枚举

【解题思路】

观察L的范围,为1~100,So it can be enumerated separatelyA’与B’的值,determine which groupA’/B’ ≥ A/B,并找出A’/B’- A/Bthe smallest set of values.
对于A’与B’是否互质,It can be determined in advance whether the greatest common divisor of the two is 1.
You can actually not do this step.由于A’与B’They are all traversed from small to large,对于A’/B’the same ratio,Must be traversed firstA’与B’互质的情况,Then traverse to the case where the two are not mutually prime.Only need to use when finding the minimum value’<',The former case can be taken without the latter case.

【题解代码】

解法1：Use the greatest common divisor function to determine whether the two are relatively prime

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
int gcd(int a, int b)
{
    
	if(b == 0)
		return a;
	return gcd(b, a%b);
}
int main()
{
    
    int a, b, l, ri, rj;//ri,rj记录结果 
    double d, d1, mind = INF;//mind:最小差值 
    cin >> a >> b >> l;
    d = (double)a/b;//A/B
    for(int i = 1; i <= l; ++i)
        for(int j = 1; j <= l; ++j)
        {
    //i:A' j:B'
        	if(gcd(i, j) == 1)//最大公约数为1,二者互质
        	{
    
	            d1 = (double)i/j;
	            if(d1 >= d && d1-d < mind)
	            {
    
	                mind = d1-d;
	                ri = i;
	                rj = j;
	            }
	    	}
        }
    cout << ri << ' ' << rj;
    return 0;
}

解法2：Do not judge mutual quality

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
int main()
{
    
    int a, b, l, ri, rj;//ri,rj记录结果 
    double d, d1, mind = INF;//mind:最小差值 
    cin >> a >> b >> l;
    d = (double)a/b;//A/B
    for(int i = 1; i <= l; ++i)
        for(int j = 1; j <= l; ++j)
        {
    //i:A' j:B'
            d1 = (double)i/j;
            if(d1 >= d && d1-d < mind)
            {
    
                mind = d1-d;
                ri = i;
                rj = j;
            }
        }
    cout << ri << ' ' << rj;
    return 0;
}