枚举和运用位运算性质。题意:给你一个数N(0 < N <= 10^10),请你找到1~N中找到数M满足M与N的最大公约数等于M与N异或的值,求M的个数并升序输出它们。
我的解题思路:首先注意数据范围已经超过32位整型了,所以要用64位整型。由于数据范围太大所以我们不能够直接枚举M然后求M与N的最大公约数是否等于M与N异或的值。不过我们可以直接枚举最大公约数,也就是枚举N的约数。因为N与M的最大公约数也是N与M异或的值,根据异或的性质:如果A XOR B = C,那么C XOR B = A,我们可以把最大公约数与N异或从而得到M的值然后判断M与N的最大公约数是否时我们枚举的这个最大公约数。到了这里,基本就可以解题了,但是还要注意几个方面的问题,一、最大公约数肯定不大于N和M;二、M肯定不大于N;三、枚举约数的复杂度是根号N,因为如果X是N的约数,那么N
/ X也是N的约数。
我的解题代码:
#include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cmath> #include <algorithm> using namespace std; typedef long long Long; const int N = 1000000; Long ans[N], ansn; Long n; void DataProcess(); Long Gcd(Long a, Long b) { return b == 0 ? a : Gcd(b, a % b); } int main() { while (~scanf("%lld", &n)) { DataProcess(); } return 0; } void DataProcess() { static int tn = 1; ansn = 0; printf("Case #%d:\n", tn++); Long cnt = (Long)sqrt(n + 0.5) + 1; for (Long i=1; i<cnt; ++i) { if (n % i == 0) { Long m = n ^ i; Long g = i; if (g == Gcd(n, m) && m <= n && g <= m) ans[ansn++] = m; m = n ^ (n / i); g = n / i; if (g == Gcd(n, m) && m <= n && g <= m) ans[ansn++] = m; } } sort(ans, ans + ansn); printf("%lld\n", ansn); for (Long i=0; i<ansn; ++i) { printf("%lld%c", ans[i], i + 1 == ansn ? '\n' : ' '); } if (ansn == 0) puts(""); return; }