c160 - NOIP2014 2.比例简化
題目描述
題目要求將給定的兩個正整數 A 和 B 的比例化簡為 A' : B'，其中 A' 和 B' 均不超過上限 L，且 A' 和 B' 互質。目標是找到滿足條件的 A' 和 B'，使得 A'/B' ≥ A/B 且 A'/B' - A/B 的值最小。
解題思路
解題思路是枚舉所有可能的 A' 和 B'，然後檢查它們是否滿足條件。具體來說，我們枚舉所有小於等於 L 的正整數 i 和 j，計算它們的最大公約數。如果 i 和 j 互質，我們計算 i/j 的值，並檢查它是否大於或等於 A/B。如果滿足這個條件，我們計算 i/j - A/B 的值，並更新答案，如果這個值比之前的答案小。
複雜度分析
- 時間複雜度: O(L^2 * log(L))。外層兩個迴圈枚舉 i 和 j，時間複雜度為 O(L^2)。在迴圈內部，計算 gcd(i, j) 的時間複雜度為 O(log(L))。
- 空間複雜度: O(1)。程式只使用了常數個變數。
程式碼
#include <iostream>
using namespace std;
int gcd(int a, int b){
if (b)
while((a %= b) && (b %= a));
return a + b;
}
int main(){
float a,b,ans=1000000;
int l,ans1=0,ans2=0;
cin >> a >> b >> l;
float s=a/b;
for(int i=1;i<=l;++i){
for(int j=1;j<=l;++j){
if(gcd(i,j)==1){
float ii=i,jj=j,ss=ii/jj;
if(ss>=s){
ss-=s;
if(ss<ans){
ans1=i;
ans2=j;
ans=ss;
}
}
}
}
}
cout << ans1 << " " << ans2;
}