rsazid99's blog

An interesting problem on number Theory(help) : Uva12716 — GCD XOR
By rsazid99, history, 7 years ago, In English

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

2

7

20000000

Sample Output

Case 1: 4

Case 2: 34866117

Link:https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4454

i am not getting any idea, how to solve this problem. Thanks in Advance :)

  • Vote: I like it
  • +24
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
7 years ago, # |
← Rev. 2   Vote: I like it +31 Vote: I do not like it

I have a solution in time and O(N) space. It should TLE because N is very high but I feel like I'm not far from the actual solution and maybe someone could continue me:

First, we can observe that, gcd(A, B) ≤ A - B, and AxorB ≥ A - B. Therefore, the pairs (A, B) must satisfy gcd(A, B) = AxorB = A - B.

For a gcd value g, the form of pairs that their gcd is equal to their difference, and is equal to g, are of the form (g * (X + 1), g * X). For the xor I've yet to find some generalization.

Here's what you can do: Create a table T[N] initialized to 0. for each pair (A,B) we find, we will increment T[A] by 1. Here's how we find those pairs:

For every gcd g from 1 to N, go over all pairs of the form (g * (X + 1), g * X) (There will be N / g of them). If the current pair has a xor equal to g, increment T[g * (X + 1)] by 1.

The amount of pairs you will go through is .

After this, maintain the partial sum of the array T: (the following is with 1-indexing)

for (int i = 2; i <= N; i++)
    T[i] += T[i - 1];

Then you can answer each query in O(1) by just outputing T[z] where z is the value given in the query.

Correct me if I'm wrong somewhere.

Edit: Actually there's a time limit of 5 seconds, and the preprocessing doesn't have a high constant, so it might fit in the time limit.

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    Here's a short c++ implementation of the above solution:

    #include <iostream>
using namespace std;

const int N = 3e7 + 1;
int T[N] = {}, q, z;

int main() {
	for (int g = 1; g < N; g++)
		for (int x = 1; g*x + g < N; x++)
			if (((g*x + g) ^ (g*x)) == g) T[g*x + g]++;
	for (int i = 2; i < N; i++) T[i] += T[i - 1];

	cin >> q;
	for (int i = 1; i <= q; i++) {
		cin >> z;
		cout << "Case " << i << ": " << T[z] << endl;
	}
}
    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Noam527

    First, we can observe that, gcd(A, B) ≤ A - B, and AxorB ≥ A - B. Therefore, the pairs (A, B) must satisfy gcd(A, B) = AxorB = A - B.

    Hmmm, is there a theory behind this part? or did you just observe and notice this one? Curious x) .

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it +2 Vote: I do not like it

      For the gcd part: suppose gcd(A, B) = g. If we divide both by g, their difference will be divided by g as well (and still be an integer). So how can their gcd by higher than their difference? Well something I just noticed (an edge case I didn't mention but doesn't matter) is if A = B. But in this case, gcd(A, B) = A, and A xor B = 0, so there are no such pairs.

      For the xor part: suppose we want A xor B to be smaller than A — B, or in other words, minimal. Xor inverts bits, so in order to make the xor operation subtract as much as it can from A, all B's set bits must be also set in A. This makes their xor A — B and this is the minimal achievable.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Nice explanation. Never thought of that xor property before.

        → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 3   Vote: I like it +7 Vote: I do not like it

      A more rigorous way to prove these claims:

      divides any linear combination of A and B. Assuming A > B,

      It's fairly straightforward that . Then

      → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    Your solution could be improved by using the fact that iff . Since , then . This is satisfied when g&B = 0 or g&(X·g) = 0. After some investigation it seems that the solutions to this equations are periodic with a period of at most . This means that the total number of operations is . This is quite borderline but still an improvement from

    → Reply