けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AOJ 1131 Unit Fraction Partition (ICPC 国内予選 2004 C)

有理数ライブラリ整備とか大げさなことせずに全探索頑張るのが本筋であろうが、ここでは有理数ライブラリの足し算の verify としてやってみた。

問題へのリンク

問題概要

有理数 p/q を

  • n 個以下の 1/r な形の有理数の和として
  • 分母 r の積が a 以下となるように

分解する方法の数を答えよ。

考えたこと

有理数ライブラリの verify として。ただし毎回「約分」をしていたら TLE したので、約分は外した。。。

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <algorithm>
using namespace std;

// 有理数
long long calc_gcd(long long a, long long b) {return b ? calc_gcd(b, a % b) : a;}
struct frac {
    long long first, second;

    using D = long double;
    inline frac normalize() {
        if (second < 0) {first = -first; second = -second;}
        //long long d = calc_gcd(first, second);
        //if (d == 0) {first = 0; second = 1;}
        //else {first /= d; second /= d;}
        return *this;
    }
    frac(long long f = 0, long long s = 1) : first(f), second(s) { normalize(); }
    inline D to_d() const { return D(first) / second; }
    inline frac operator - () { (*this).first *= -1; return (*this); }
    inline const frac& operator = (long long a) { *this = frac(a, 1); return *this; }
    inline const frac& operator += (const frac& a);
    inline const frac& operator += (long long a);
    inline const frac& operator -= (const frac& a);
    inline const frac& operator -= (long long a);
    inline const frac& operator *= (const frac& a);
    inline const frac& operator *= (long long a);
    inline const frac& operator /= (const frac& a);
    inline const frac& operator /= (long long a);
    inline friend ostream& operator << (ostream& s, const frac& f) { 
        s << f.first; if (f.second != 1) s << "/" << f.second; return s;
    }
};
inline bool operator == (const frac &a, const frac&b) {
    return a.first * b.second == a.second * b.first;
}
inline bool operator != (const frac &a, const frac &b) { return !(a == b); }
inline bool operator < (const frac& a, const frac& b) {
    return a.first * b.second < a.second * b.first;
}
inline bool operator > (const frac& a, const frac& b) { return b < a; }
inline bool operator <= (const frac& a, const frac& b) {
    return a.first * b.second <= a.second * b.first;
}
inline bool operator >= (const frac& a, const frac& b) { return b <= a; }
inline frac operator + (const frac& a, const frac& b) {
    frac res;
    res.first = a.first * b.second + a.second * b.first;
    res.second = a.second * b.second;
    res.normalize();
    return res;
}
inline frac operator - (const frac& a, const frac& b) {
    frac res;
    res.first = a.first * b.second - a.second * b.first;
    res.second = a.second * b.second;
    res.normalize();
    return res;
}
inline frac operator * (const frac& a, const frac& b) {
    frac res;
    res.first = a.first * b.first;
    res.second = a.second * b.second;
    res.normalize();
    return res;
}
inline frac operator / (const frac& a, const frac& b) {
    frac res;
    res.first = a.first * b.second;
    res.second = a.second * b.first;
    res.normalize();
    return res;
}
inline frac abs(const frac& a) {
    frac res; res = a; res.normalize(); 
    if (res.first < 0) res.first = res.first * (-1);
    return res;
}
inline const frac& frac::operator += (const frac& x) {*this = *this + x; return *this;}
inline const frac& frac::operator += (long long x) {*this = *this + x; return *this;}
inline const frac& frac::operator -= (const frac& x) {*this = *this - x; return *this;}
inline const frac& frac::operator -= (long long x) {*this = *this + x; return *this;}
inline const frac& frac::operator *= (const frac& x) {*this = *this * x; return *this;}
inline const frac& frac::operator *= (long long x) {*this = *this * x; return *this;}
inline const frac& frac::operator /= (const frac& x) {*this = *this / x; return *this;}
inline const frac& frac::operator /= (long long x) {*this = *this / x; return *this;}



int p, q, a, n;
int rec(frac f, int con, int bunbomax, int mul) {
    if (con == 0) { // 残り 0 回だったら f = 0 じゃなきゃダメ
        if (f == 0) return 1;
        else return 0;
    }
    if (f == 0) return 1; // 0 になったら終わり

    int res = 0;
    for (int i = a/mul; i >= bunbomax; --i) {
        if (f < frac(1, i)) break;
        res += rec(f - frac(1, i), con - 1, i, mul * i);
    }
    return res;
}


int main() {
    while (cin >> p >> q >> a >> n, n) {
        frac start(p, q);
        int res = rec(start, n, 1, 1);
        cout << res << endl;
    }
}