solution1
直观上的分数处理
#includeusing namespace std; int main() { printf("1048575/524288"); return 0; }
#include#include typedef long long ll; struct fraction{ll up, down; }; ll gcd(ll a, ll b){if(!b) return a; return gcd(b, a % b); } fraction r(fraction f){if(gcd(f.down, f.up) > 1){f.down /= gcd(f.down, f.up); f.up /= gcd(f.down, f.up); } return f; } fraction add(fraction f1, fraction f2){fraction f; f.down = f1.down * f2.down; f.up = f1.up * f2.down + f2.up * f1.down; return r(f); } int main(){fraction f, t; f.up = f.down = 1; for(ll i = 2; i <= pow(2, 19); i *= 2){t.up = 1; t.down = i; printf("%lld %lld\n", t.down, f.up); f = add(f, t); } printf("%lld %lld, %lld %lld", f.up / f.down, f.up % f.down, f.up, f.down); return 0; }
solution2
手动通分计算为
(219+218+217……+20)/219= (220-1)/219
- 20+21+22+……+2n-1 = 2n-1
- 较大的数若比 较小的数 的两倍大于或者小1,则两者互质
#include
#include typedef long long ll; int main(){printf("%lld/%lld", (ll) pow(2, 20) - 1, (ll) pow(2, 19));//注意别漏了强转double -> ll return 0; }