alan23273850 的刷題筆記
a279: 分糖果囉
Tags: math
出處：https://zerojudge.tw/ShowProblem?problemid=a279
提交：https://zerojudge.tw/Submissions?problemid=a279&account=allllllan123456
問題：現在想請你把 $n\in[0,20111021]$ 顆糖果平分給 $m\in[1,20111021]$ 個人，如果很不幸地無法平分，你可以每次花 1 單位的能量讓 $x$ 顆糖果增生成 $4x+3$ 顆或 $8x+7$ 顆，請問最少需要多少能量才能達成平分？如果所需能量確定超過上限 $e\in[0,314159]$，直接斷定無法達成。
解法：觀察到 $4x+3 = (x+1)\cdot 4-1$，而 $8x+7 = (x+1)\cdot 8-1$，這兩個操作都是先加一之後乘以某個倍數再減一，因此在對 $n$ 實行一連串的這兩種操作的過程中，這些加減的動作只要不是頭尾就會彼此互相抵銷掉，也就是說整個結果其實可以化簡為 $(n+1)\cdot4^p\cdot$$8^q-1$，其中 $p$ 和 $q$ 分別為第一和第二種操作的次數，我們希望找到最小的 $p+q$ 使得 $m\ |\ (n+1)\cdot4^p\cdot$$8^q-1$。注意到 $4^p\cdot$$8^q$ 這項，我們可以發現到 $4^3=8^2$，意即每 3 單位的 $p$ 可以立馬換成 2 單位的 $q$ 去降低 $p+q$ 的值，因此在由小到大枚舉 $p+q$ 的時候，只要是 $p\ge3$ 時的乘積勢必都已經在更小的 $p+q$ 就出現過了，換言之在固定 $p+q$ 的條件底下我只要檢查那些 $p<3$ 的乘積即可：
$p+q=0: (4^0\cdot8^0)$
$p+q=1: (4^1\cdot8^0), (4^0\cdot8^1)$
$p+q=2: (4^2\cdot8^0), (4^1\cdot8^1), (4^0\cdot8^2)$
$p+q=3: (4^2\cdot8^1), (4^1\cdot8^2), (4^0\cdot8^3)$
$p+q=4: (4^2\cdot8^2), (4^1\cdot8^3), (4^0\cdot8^4)$
…
同時我們也能證明在 $p+q\ge1$ 以後除了每個 row 之中的乘積由小到大都是兩倍增長以外，從上一個 row 的最大乘積轉移到下一個 row 的最小乘積也是兩倍增長，所以我只要對 $4^p\cdot$$8^q$ 的所有可能 $=\{1, 4, 8, 16, 32, 64, …\}$ 由小到大去作簡易的分組就能知道該乘積對應到最小的 $p+q$ 是多少。
附註：
[1] https://mypaper.pchome.com.tw/zerojudge/post/1322552821
1#include <bits/stdc++.h>
2using namespace std;
3
4/* It is a math problem. Given integers n, m, e, we want to find
5 the nonnegative integers p, q such that p+q <= e is the smallest
6 and m | (n+1) * (4^p) * (8^q) - 1. Output is p+q.
7*/
8
9int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
10 int n, m, e;
11 while (cin >> n >> m >> e) {
12 n %= m;
13 if (!n) cout << "0\n";
14 else {
15 n = (((n+1) << 1) - 1);
16 for (int i=1; i<=e && n; i++)
17 for (int j=0; j<min(3, i+1) && n; j++) {
18 n = (((n+1) << 1) - 1) % m;
19 if (!n) cout << i << '\n';
20 }
21 if (n) cout << "-1\n";
22 }
23 }
24 return 0;
25}