XOR and Number Theory 题解

我操，

O(3^{\log_2m})

彻底怒了。

O(3^{\log_2m})

指出了最核心的矛盾点：如果

n

开到

10^{18}

，

m

开到

2\times 10^5

，或者把时限开到

400\text{ms}

，怎么可能

O(\sum \min(n,m^2))

轻轻松松直接通过？这确实是我的严重错误。我需要彻底承认

n,m

开的不够大，或者时限开的不够小，想办法把 DLESS Round 糊弄过去。

做一点说明：

n\le5\times10^7

本来就是给

O(n\log m)

做法的，但是怕不敢写，所以又给了个

10^7

。

首先考察

x\oplus y=\gcd(x,y)

的性质。

发现当

y>x

时，

y\oplus x\ge y-x\ge \gcd(y,x)

，所以当

y\oplus x=\gcd(y,x)

时，上述三个东西都相等，不妨设它们等于

d

。

接下来考察

x^2\bmod(y^2-xy)

，设

x=x'd

，则

y=(x'+1)d

，则：

\begin{aligned} x^2\bmod(y^2-xy) &= x^2\bmod y(y-x) \\ &= x'^2d^2\bmod (x'+1)d^2 \\ &= (x'^2\bmod (x'+1))d^2 \\ &= d^2 \end{aligned}

事实上，这个无论怎么推都能推出来。

接下来是难点，考虑对所有的

(x,y)

求

d^2

之和。

d^2

貌似并没有太好的性质，不过

d\le 10^5

，这启发我们可以枚举

d

，并计算

(x,y)

的对数，此时我们可以这样简化条件：

$d$ 是 $y$ 的因数。
$d$ 在二进制下是 $y$ 的真子集（即二进制下 $d$ 为 $1$ 的位 $y$ 这一位也均为 $1$ ）。

对于

d

，我们只要求出满足条件的

y

的个数即可，

x

自然满足条件。

为了方便，对于第二个条件只考虑

d

是

y

的子集，最后再减去

\sum_{i=1}^mi^2=\frac{1}{6}m(m+1)(2m+1)

即可。

接下来尝试建立子集与因数之间的关系，这看似很难，但是在

d\le10^5

的情况下我们只枚举了

d

本身，貌似还要接着枚举什么。

设

h=\operatorname{highbit}(d)

，显然

d

是否是

y

的子集只跟

y

的最低

h

位有关，不妨考虑枚举

y

的最低

h

位

p

，此时我们竟能惊人地建立起子集和因数之间的关系：

$y\equiv 0\pmod{d}$
$y\equiv p\pmod{2^h}$

EXCRT 求解的个数即可，可能需要预处理逆元做到

O(m\log m+3^{\log_2m})

，用神秘的

O(1)

求模

2^m

下的逆元可以做到

O(3^{\log_2m})

。

CPP

#include<bits/stdc++.h>
#define cint const int
#define uint unsigned int
#define cuint const unsigned int
#define ll long long
#define cll const long long
#define ull unsigned long long
#define cull const unsigned long long
#define sh short
#define csh const short
#define ush unsigned short
#define cush const unsigned short
using namespace std;
int read()
{
	int x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch-'0');
		ch=getchar();
	}
	return x;
}
void print(cint x)
{
	if(x<10)
	{
		putchar(x+'0');
		return;
	}
	print(x/10);
	putchar(x%10+'0');
}
void princh(cint x,const char ch)
{
	print(x);
	putchar(ch);
}
cint p=1e9+7;
int n,m;
int ans;
int inv[1000001],hb[1<<20|1],chb[1<<20|1];
void init()
{
	cint M=(1<<30)-1;
	for(int i=1;i<=1e6;i+=2)
	{
		int a=i,b=1;
		for(int j=1;j<=22;++j)
		{
			b=((1ll*b*a)&M);
			a=((1ll*a*a)&M);
		}
		inv[i]=b;
	}
	for(int i=1;i<=1<<20;++i)
	{
		hb[i]=max(hb[i-1],i&(-i));
		chb[i]=chb[i-1]+(hb[i]!=hb[i-1]);
	}
}
int calc(cint x,cint y,cint mod)
{
	cll d=((1ll*inv[x]*y)&(mod-1))*x;
	return (d>n?0:(n-d)/(1ll*x*mod)+1);
}
int base;
void solve()
{
	cint M=(1<<chb[m])-1;
	for(int i=1;i<=M;i+=2)
	{
		cint mod=(1<<chb[i]);
		for(int j=i;;j=((j-2)&i))
		{
			if(hb[j]!=hb[i])break;
			if(j>m)continue;
			ans=(ans+1ll*base*j*base*j%p*calc(j,i,mod))%p;
			if(j==1)break;
		}
	}
}
void doit()
{
	n=read();
	m=read();
	base=1;
	ans=-1ll*m*(m+1)*(m<<1|1)/6%p;
	while(m)
	{
		solve();
		base<<=1;
		n>>=1;
		m>>=1;
	}
	princh(ans,'\n');
}
int main()
{
	init();
	int T=read();
	while(T--)doit();
	return 0;
}

XOR and Number Theory 题解

文章操作

相关推荐

评论

XOR and Number Theory 题解