Codeforces Round 901 (Div. 2) - C. Jellyfish and Green Apple - 思维+位运算

方法一：
很强大的思路。按照题目最原始的暴力求解方法，同时考虑了只能苹果二分这一性质，排除了输出-1的情况。

#include 
using namespace std;
#define ll long long
#define sf(x) scanf("%d", &x);
#define de(x) cout << x << " ";
#define Pu puts("");
const int N = 1e5 + 9, mod = 1e9 + 7;
ll n, m, ans;
int lowbit(ll x) {
    return x & (-x);
}  // 如果二进制是110 则返回4，计100
int main() {
    int T;
    cin >> T;
    while (T--) {
        cin >> n >> m;
        // https://blog.csdn.net/WindFromAS/article/details/133457968
        // 参考思路一：思维+位运算
        if (lowbit(m / __gcd(n, m)) != m / __gcd(n, m)) {
            printf("-1\n");
            continue;
        }
        ans = 0;
        n %= m;
        while (n) {
            ans += n;
            n *= 2;
            n %= m;
        }
        printf("%lld\n", ans);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

做法二：
思路也很巧妙，先把苹果分成一定满足条件的很多小片，然后进行合并。
参考博客：
https://zhuanlan.zhihu.com/p/659201094

#include 
using namespace std;
#define ll long long
#define sf(x) scanf("%d", &x);
#define de(x) cout << x << " ";
#define Pu puts("");
const int N = 1e5 + 9, mod = 1e9 + 7;
ll n, m, ans;
int main() {
    int T;
    cin >> T;
    ll t;     // 最大公因数，即最多情况下苹果的片数
    ll x, y;  // x表示每个苹果分的最大片数，y表示每个人能拿到的最多片数
    while (T--) {
        cin >> n >> m;
        if (n % m == 0) {
            printf("0\n");
            continue;
        }
        n %= m;
        t = n * m / __gcd(n, m);
        x = t / n;
        if (x & (x - 1)) {
            printf("-1\n");
            continue;
        }
        y = t / m;
        ll res = 0;  // 对很多小片进行合并，y中1的个数即为每个苹果需要切的刀数
        // 因为我们在前面已经判断了所有苹果一定能否切成t片
        // 所以此时我们只需要尽可能的合并，2合并为1（少1刀），4合并为1（少3刀）
        while (y) {
            if (y & 1)
                res++;
            y >>= 1;
        }
        ans = res * m - n;
        // cout << ans << endl;
        printf("%lld\n", ans);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41