UVA12716 GCD XOR

题目地址

题目链接

题解

神仙结论，完全不会

[large{ 设a space xorspace b = c\ 则有a - b<=c\ 可以设a=k_1c,b=k_2b,则a-b=(k_1-k_2)c\ 所以a-b>=c\ 联立两式 egin{cases} a-b<=c\ a-b>=c end{cases}可得a-b=c\ 又因为gcd(a,b)=gcd(a,a-c)=c\ 所以只需要枚举a,c，验证[aspace xorspace (a-c)=c]即可 } ]

#include <bits/stdc++.h>
using namespace std;

#define I_int int
inline I_int read() {
       I_int x = 0 , f = 1 ; char c = getchar() ;
    while( c < '0' || c > '9' ) { if( c == '-' ) f = -1 ; c = getchar() ; } 
    while( c >= '0' && c <= '9' ) { x = x * 10 + c - '0' ; c = getchar() ; } 
    return x * f ;
} 
#undef I_int

#define ll long long
const int N = 3 * 1e7 + 10;

int T, ans[N];

void init() {
	for(int c = 1; c < N / 2; ++c) {
		for(int a = 2 * c; a < N; a += c) {
			int b = a - c;
			if(c == (a ^ b)) ++ans[a];
		}
	}
	for(int i = 1; i < N; ++i) ans[i] += ans[i - 1];
}

int main() {
	init();
	T = read();
	int C = 0;
	while(T--) {
		int n = read();
		printf("Case %d: %d
", ++C, ans[n]);
	}
}