異或

jzoj 2298

題目大意：

定義$nb$數(shù)對(duì)$a,b$為$gcd(a,b)=a^b$的數(shù)對(duì)，問(wèn)不大于$n$的$nb$數(shù)對(duì)有多少對(duì)

輸入樣例#1

12

輸出樣例#1

8

輸入樣例#2

123456

輸出樣例#2

214394

數(shù)據(jù)范圍

測(cè)試點(diǎn)數(shù)據(jù)規(guī)模

1	10
2	100
3	1000
4	5000
5	10000
6	100000
7	500000
8	1000000
9	5000000
10	20000000

解題思路：

我們第一個(gè)想到的就是暴力枚舉每一個(gè)數(shù)對(duì)，然后判斷，時(shí)間復(fù)雜度$o(n^{2}lo{g}_n)$會(huì)TLE
因?yàn)?span id="ze8trgl8bvbq" class="katex--inline">$axorb=c$，則$axorc=b$，所以我們可以枚舉c，然后在枚舉a是c的幾倍，然后用公式求出b，然后再求gcd，判斷是否和c一樣，時(shí)間復(fù)雜度$o(n(lo{g}_n{)}^2)$,也會(huì)TLE
我們可以經(jīng)過(guò)證明得知b=a-c
證明：
首先$a?b?axorb$
我們距離兩個(gè)二進(jìn)制數(shù)：
$10110$
$11000$
他們相減是$2$
$xor$是14
我們可以發(fā)現(xiàn)$xor$是不同位的和
而相減是加某些不同位，再減某些不同位，最大就是所有不同位加，也不大于$xor$
所以$a?b?axorb$
然后我們可以發(fā)現(xiàn)$a?b?c$
我們也列兩個(gè)例子:
$a=12$
$b=9$
$c=3$
我們?cè)O(shè)$as=a/c=4$
$bs=b/c=3$
因?yàn)閍,b都是c的倍數(shù)，所以$a?b=as?c?bs?c=(as?bs)?c$
因?yàn)?span id="ze8trgl8bvbq" class="katex--inline">$a$不等于$b$
所以$as?bs?1$
所以$(as?bs)?c?c$
所以$a?b?c$
假設(shè)存在$c<a?b$
則$c<a?b?axorb$
不滿足$c=axorb$
所以$c=a?b$
所以$b=a?c$
因此$gcd（a,b）=gcd(a,a?c)=c$
所以我們只需判斷是否有$c=axorb$即可

代碼：

#include<cstdio> using namespace std; int n,a,b,ans; int main() {scanf("%d",&n);for (int i=1;i<=(n>>1);++i)for (int j=2;i*j<=n;++j){a=i*j;//求出ab=a-i;//相減得到bif (i==(a^b))//判斷c是否等于a^bans++;}printf("%d",ans); }

總結(jié)

以上是生活随笔為你收集整理的【数学】异或（jzoj 2298）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。