2025牛客国庆集训派对day7 M C 个人题解

Water

exgcd #数学

标题翻译

Walk Alone 感到口渴，想要喝水。他想要恰好喝 \(x\) 单元的水，但没有符合的量杯。他只有两个水壶，容量分别为 \(A\) 和 \(B\)。他发现可以对这两个水壶举行以下操纵：

• 将此中一个水壶装满水。
  
• 将此中一个水壶中的水全部倒掉。
  
• 喝掉此中一个水壶中的全部水。
  
• 尽大概多地将水从一个水壶转移到另一个水壶，且不能溢出。情势化地说，假如两个水壶当前分别含有 \(a\) 和 \(b\) 单元的水，则他可以从 \(A\) 向 \(B\) 转移 \(\min(a, B - b)\) 单元的水，大概从 \(B\) 向 \(A\) 转移 \(\min(b, A - a)\) 单元的水。
  

Walk Alone 渴望尽大概少地操纵。你能告诉他为了喝到恰好 \(x\) 单元的水所需的最少操纵次数吗？
输入形貌

输入包罗多个测试用例。
第一行包罗一个整数 \(T\)，表现测试用例的数目。
每个测试用例仅有一行，包罗三个整数 \(A\)、\(B\) 和 \(x\)，分别表现两个水壶的容量以及他须要喝的水的体积。
输出形貌

对于每个测试用例，输出一行一个整数，表现最少操纵次数。假如无法喝到恰好 \(x\) 单元的水，输出 \(-1\)。
思绪

全部的倒水操纵现实上可以转化为：

\[Ax+By=C\]

• 此中\(C\)为须要构造的数字
  
• \(x,y\in Z\)
  

对于一次\(x\pm 1\)，现实上须要两次操纵
以是答案可以分类讨论：
<ul>当\(x\geq 0\&\&y\geq 0\)，\(ans=2(|x|+|y|)_{min}\)
否则\(ans=2(|x|+|y|)_{min}-1\)<ul>
这是由于\(x\cdot y> x;            q[l].push_back({ 1,i,m,x });            q[r + 1].push_back({ 1,i,m,-x });        } else {            int l, r;cin >> l >> r;            q[l].push_back({ 2,i,m,-k });            q[r + 1].push_back({ 2,i,m,k });        }    }    int ans = 0, d = 0;    rep(i, 1, n) {        for (auto [op, l, r, x] : q) {            if (op == 1) {                update(1, 1, m, l, r, x);            } else {                if (x < 0)d++;                else d--;                update(1, 1, m, l, r, x);            }        }        int del = -min(0ll, mi[1]);        ans += d - (del + k - 1) / k;    }    cout  t;    while (t--)solve();    return 0;}[/code]