2014-05-19

UVa 12716 - GCD XOR

1. Problem
2. Input
3. Output
4. Sample Input
5. Sample Output
6. Solution

Problem

Given an integer N, Find how many pairs (A, B) are there such that gcd(A, B) = A xor B where 1 < B < A <= N. Here gcd(A, B) means the greatest common divisor of the numbers A and B. And A xor B is the value of the bitwise xor operation on the binary representation of A and B.

Input

The First line of the input contains an integer T (T < 10000) denoting the number of test cases. The following T lines contain an integer N (1 <= N <= 30000000).

Output

For each test case, print the case number first in the format, Case X: (here, X is the serial of the input) followed by a space and then the answer for that case.
There is no new-line between cases.

Explanation
Sample 1:
For N = 7, there are four valid pairs: (3, 2), (5, 4), (6, 4) and (7, 6).

Sample Input

1
2
3

2
7
20000000

Sample Output

1 2	Case 1: 4 Case 2: 34866117

Solution

首先，嘗試把 N <= 1000 的情況列下來，列出 gcd(A, B) = C = A xor B

其中滿足 B < A and A mod C = 0，然後我們又觀察到 A&C == C，也就是說看 bitmask 的話，C 是 A 的 subset。

經由這一點，我們可以先寫出一個不會過 (TLE) 的做法，對 A 找到所有因子 C，查看是否符合 A&C == C，但是這樣的做法很容易知道時間效率不夠好。

下面是一個最簡單的版本。

TLE version

#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
#define maxL (30000000>>5)+1
#define GET(x) (mark[(x)>>5]>>((x)&31)&1)
#define SET(x) (mark[(x)>>5] |= 1<<((x)&31))
int mark[maxL];
int P[5500], Pt = 0;
int F[30000005] = {};
void sieve() {
    register int i, j, k, l;
    SET(1);
    int n = 50000;
    for(i = 2; i <= n; i++) {
        if(!GET(i)) {
            for(j = i + i; j <= n; j += i)
                SET(j);
            P[Pt++] = i;
        }
    }
}
vector< pair<int, int> > factor(int n) {
    int on = n;
    vector< pair<int, int> > R;
    
    for(int i = 0, j; i < Pt && P[i] * P[i] <= n; i++) {
        if(n%P[i] == 0) {		
            for(j = 0; n%P[i] == 0; n /= P[i], j++);
            R.push_back(make_pair(P[i], j));
        }
    }
    if(n != 1)	R.push_back(make_pair(n, 1));
    return R;
}
void make(int idx, int n, int m, vector< pair<int, int> > &v) {
    if(idx == v.size()) {
        if((n&m) == m)
            F[n]++;
        return;
    }
    int a = m, b = v[idx].first;
    for(int i = v[idx].second; i >= 0; i--)
        make(idx + 1, n, a, v), a *= b;
}
int main() {
    sieve();
    vector< pair<int, int> > ff;
    for(int i = 1; i <= 30000000; i++) {
        ff = factor(i);
        make(0, i, 1, ff);
    }
    int testcase, cases = 0, n;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d", &n);
        int ret = 0;
        for(int i = 1; i <= n; i++)
            ret += F[i];
        printf("%d\n", ret - n);
    }
    return 0;
}

接著，使用其他的考慮方式，既然 (n, n + 1) 是已知解，其倍數解 (kn, k(n + 1))也是考量的一部分。

總歸一句，觀察 orz。

accepted

#include <stdio.h>
using namespace std;
int F[30000005] = {};
int main() {
    for(int i = 1; i <= 30000000; i++) {
        for(int j = i << 1; i + j <= 30000000; j += i) {
            if(((i + j)&(j)) == j)
                F[i + j]++;
        }
    }
    for(int i = 1; i <= 30000000; i++)
        F[i] += F[i-1];
    int testcase, cases = 0, n;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d", &n);
        printf("Case %d: %d\n", ++cases, F[n]);
    }
    return 0;
}

Morris' Blog