Codeforces Round 901 (Div. 2)

Codeforces Round 901 (Div. 2)"/>

Codeforces Round 901 (Div. 2)

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

#include <bits/stdc++.h>
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;// // 参考思路一：思维+位运算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;
}

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

#include <bits/stdc++.h>
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;
}