題目地址：http://www.spoj.com/problems/FINFRAC/

題目大意：

給4個整數a,b,c,d，尋找兩個整數p，q，使得a/b < p/q < c/d，需要q是最小的，如果存在多個解，那么找到p是最小的。

?

連分數解法：

設[a/b]表示a/b向下取整

如果a/b >= 1，設k = [a/b]，可以知道 ( a/b ) - k < ( p/q ) - k < ( c/d ) - k，即 (a-bk)/b < (p - qk)/q < ( c- dk) / d，設a' = a - bk，p' = p - qk，c' = c - dk，則求出a'/b < p'/q < c'/d的解以后，p = p' + qk，可以得到真實的p和q。

如果a/b<1

如果c/d>1，那么p = q = 1

如果c/d<=1，那么問題可以轉化為d/c < q/p < b/a

?

欲知詳解請猛戳這里

#include <iostream>using namespace std; typedef long long LL;LL find(LL a,LL b,LL c,LL d) {if(a<b){if(c>d) return 1;else return find(d,c,b,a)*d/c+1;}else{LL k=a/b;return find(a-k*b,b,c-k*d,d);} }int main() {LL a,b,c,d,p,q;while(cin>>a>>b>>c>>d){q=find(a,b,c,d);p=q*a/b+1;cout<<p<<"/"<<q<<endl;}return 0; }

?

超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生

總結

以上是生活随笔為你收集整理的SPOJ Finding Fractions的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。