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;
}
更多推荐
Codeforces Round 901 (Div. 2)
发布评论