经验总结

  1. 首页 > 生活 > >

Div. 2 Codeforces Round #833 A-D.md( 二 )

生活百科


我们尝试直接求出这个 \(p\) ：
\[\begin{aligned} p\cdot 2^{30} + (2^{30} - 2^k) &\equiv 0 & &\pmod d\\ p\cdot 2^{30-k} + (2^{30-k} - 1) &\equiv 0 & &\pmod{\frac{d}{2^k}}\\ p &\equiv \bigg(\frac{1}{2} \bigg)^{30-k} - 1 & &\pmod{\frac{d}{2^k}}\\ p &\equiv \bigg(\frac{\frac{d}{2^k}+1}{2} \bigg)^{30-k} - 1 + \frac{d}{2^k} & &\pmod{\frac{d}{2^k}}\\\end{aligned}\]【Div. 2 Codeforces Round #833A-D.md】时间复杂度 \(O(1)\)
空间复杂度 \(O(1)\)
代码方法一#include <bits/stdc++.h>#define ll long longusing namespace std;bool solve() {int a, b, d;cin >> a >> b >> d;int k = __builtin_ctz(d);if (k > __builtin_ctz(a) || k > __builtin_ctz(b)) return false;ll x = 0;for (int i = k;i < 30;i++) if (!(x & (1 << i))) x += (ll)d << (i - k);cout << x << '\n';return true;}int main() {std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--) {if (!solve()) cout << -1 << '\n';}return 0;}方法二#include <bits/stdc++.h>#define ll long longusing namespace std;int qpow(int a, int k, int P) {int ans = 1;while (k) {if (k & 1) ans = 1LL * ans * a % P;k >>= 1;a = 1LL * a * a % P;}return ans;}bool solve() {int a, b, d;cin >> a >> b >> d;int k = __builtin_ctz(d);if (k > __builtin_ctz(a) || k > __builtin_ctz(b)) return false;d >>= k;ll x = (qpow((d + 1) / 2, 30 - k, d) - 1 + d) % d * (1LL << 30) + (1 << 30) - (1 << k);cout << x << '\n';return true;}int main() {std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--) {if (!solve()) cout << -1 << '\n';}return 0;}

经验总结扩展阅读


上一篇：2023年7月哪几天吉日适合剖腹产

下一篇：京东双十一分几个阶段