這次的題唐完了，尤其是 T1。

再也不死磕難題了......

T1

給定一個 \(n\)。

求解 \(\sum_{a=1}^{n}\sum_{b=a+1}^{n} [gcd(a,b)=a\oplus b]\)

\(n \le 10^7\)

為什么說這個題唐呢？因為它是 \(O(nlogn)\) 的，這個數據范圍.....

先說說我的錯誤解法。

設 \(gcd(a,b)=c\)，因為寫起來方便一些。

我們發現 \(a\oplus b=c\) 可得 \(a\oplus c=b\)。

因為 \(c\) 是 \(a\) 的約數，我們可以 \(nlogn\) 枚舉，這個應該沒人不會了。

然后枚舉出來后算出 \(b\) 就行。

這個我當時以為是 \(nlogn\) 的，因為我太信任我的 gcd 板子了。

這個板子不是一般的板子，它是硬生生干過基于值域預處理的gcd。

所以平常我看它特別快，就把它當成 \(O(1)\) 的了。

但這道題時間極其極限，稍微多一點常數就會死。

所以這邊也是 60 分遺憾離場了。

其實我本來就是沖著這個 60 pts 打的，誰想得到正解就是 \(nlogn\) 啊。

那我們該怎么辦？？？

開始推式子，總體思路是不使用這個 gcd，也就是用一個 \(a,b\) 的其他式子表示出來 \(c\)。

反正我是沒能想出來的。

眾所周知，為什么異或的 latex 是 oplus？因為這個東西不就是一個不進位的加法么。

\(a-b\le a\oplus b=c\)

\(a=k_1*c, b=k_2*c\)

\(a-b=(k_1-k_2)*c\)

\(a-b>=c\)

有因為 \(a-b\le c\)

所以 \(a-b=c=a\oplus b\)。

這個判斷是 \(O(1)\) 的。

#include <bits/stdc++.h>
using namespace std;
const int MN=1e7+117;
int ans[MN+1];
int main(){
	freopen("gcdxor.in","r",stdin);
	freopen("gcdxor.out","w",stdout);
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	for(int i=1; i<=MN/2; ++i){
		for(int j=i+i; j<=MN; j+=i){
			if((i^j)==j-i) ans[j]++;
		}
	}
	for(int i=1; i<=MN; ++i) ans[i+1]+=ans[i];
	int val; cin>>val; cout<<ans[val]<<'\n';
	/*
	int T, cnttt=0; cin>>T; while(T--){
		int val; cin>>val;
		cout<<"Case "<<++cnttt<<": "<<ans[val]<<'\n';
	}
	*/
	return 0;
}