Uva12716 素数筛思想的应用

Uva12716

题意：

输入整数n，1<= n <=3e7，问有多少个整数对（a，b）满足：1 <= b <= a <= n，且gcd（a，b）== a XOR b

解法：

a^b = c 等价于a^c = b  所以枚举a和c，而a和c全部枚举肯定TLE，所以高效算法：通过c是a的约数这个关系来枚举会减小循环，必须要将c放在循环外面，因为c的情况比较少。其实本题就是要求：c=a-b（规律）,c=a^b   

/*
  打表找规律
*/
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a%b); }
const int maxn = 3e7 + 5;
int ans[maxn];

void generate() {
    //类似于筛素数，我们的外层是公约数（素数）
    //注意筛素数的时候我们先筛小的，也就是最基本的那个，这样子就可以筛掉所有最基本的那个的倍数
    for (int c = 1; c <= maxn / 2; c++) {
        for (int a = c + c; a <= maxn; a += c) {
            int b = a - c;
            if ((a^b) == c) ans[a]++;
        }
    }
    for (int i = 2; i < maxn; i++)ans[i] += ans[i - 1];
}

int main() {
    int T; scanf("%d", &T);
    int kase = 0;
    generate();
    while (T--) {
        int n; scanf("%lld", &n);
        printf("Case %d: %d
", ++kase, ans[n]);
    }
    return 0;
}