http://acm.hdu.edu.cn/showproblem.php?pid=4993

求出 后,代入通解公式

解不等式。
复杂度

(只贴出与题目有关的代码,宏定义见 GitHub

ll Qceil(ll x, ll y) {return ceil(double(x) / y - 1e-8);}

void exgcd(ll a, ll b, ll& d, ll& x, ll& y)
{
    if (!b) d = a, x = 1LL, y = 0LL;
    else exgcd(b, a % b, d, y, x), y -= x * (a / b);
}

ll get_solves(ll a, ll b, ll c)
{
    ll g, x, y;
    exgcd(a, b, g, x, y);
    if (c % g) return 0;
    a /= g, b /= g, c /= g;
    x *= c, y *= c;
    return max(Qceil(y, a) - Qceil(1 - x, b), 0LL);
}

int main()
{
    ll a, b, c;
    TT SLLL(a, b, c), PL(get_solves(a, b, c));
    return 0;
}

Comments

comments powered by Disqus