题目链接:GCD XOR - UVA 12716 - Virtual Judge (vjudge.net)
最近在看紫书的时候看到这道题,但是感觉紫书上写的有点云里雾里,对于一些“不难发现”的不等式解释不够详细,这里做一下解释。
题目大意 / Problem
给定一个正整数N,问有多少对正整数(A,B)使得\(gcd(a, b) = a\oplus b\),且有\(1 \le B \le A \le N\)。
分析 / Analyse
设\(c = a \oplus b\),则有\(b = a \oplus c\),同时又有\(c = gcd(a, b)\),则我们可以枚举c和a(\(a = k * c\)),然后算出\(b = a \oplus c\),再判断\(1\le B\le N \quad and \quad c=gcd(a, b)\)。这样时间复杂度是\(O(N(logN)^2)\)。N是3e7,非常恐怖,应该会超时。
所以我们继续优化,首先有\(a - b \le a \oplus b\),这个的证明如下:
再证明\(a - b \ge gcd(a, b)\)。
所以有c<=a-b<=c,故c=a-b。
这样只需要枚举c和a = k*c,然后算出b = a - c,再判断b = a ^ c即可。
时间复杂度为\(O(NlogN)\)。
因为有多次询问,用前缀和即可。
代码 / Code
#include <bits/stdc++.h> #define int long long using namespace std; const int maxn = 3e7 + 9; int kase = 0; int prefix[maxn]; void getprefix(int N) { for(int c = 1;c <= N; ++ c) { for(int a = c;a <= N; a += c) { int b = a - c; if(1 <= b && b <= a && (a ^ b) == c)prefix[max(a, b)] ++; } } for(int i = 1;i <= N; ++ i)prefix[i] += prefix[i - 1]; } void solve() { int N;cin >> N; cout << "Case " << ++ kase << ": " << prefix[N] << '\n'; } signed main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); getprefix(maxn - 5); int _;cin >> _; while(_ --)solve(); return 0; }
Comments NOTHING