自动搬运

查看原文

来自洛谷，原作者为

	QuantAsk 烟火里成灰，也去的完美。

搬运于2025-08-24 22:24:39，当前版本为作者最后更新于2020-10-20 07:22:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

出题人先来报个到，比赛的时候发现许多选手的做法都和我的不一样/kk。也有莫比乌斯反演过了的神仙。也十分感谢本题的验题人 beginend 和 my_dog。

T4 象棋与马

这个马能走到全图的充要条件显然是它能走到 $(0,1)$。考虑给出 $x,y$ 求它能否走到 $(0,1)$。

算法1：

暴力 bfs 看是否能到达 $(0,1)$ 或打表。

期望得分 $5pts$。

算法2：

请注意下文中 $(X,Y)$ 表示当前马的坐标，$x,y$ 表示马一步走的矩形的长和宽。

考虑从数论角度考虑本题。

首先如果当 $gcd(x,y)\neq 1$ 显然不行。

因为走的顺序时无所谓的，所以可以将走的路程分成两段，一段只有是 $(X\pm x,Y\pm y)$ 的位移，一段是只有 $(X\pm y,Y\pm x)$ 的位移。

显然对于第一段能走到的点可以表示为 $(2ax,2cy)$ 或 $(2ax+x,2cy+y)$。第二段同理为 $(2by,2dx)$ 或 $(2by+y,2dx+x)$。其中 $a,b,c,d\in \mathbb{Z}$。那么我们可以推出公式有

$$\left\{\begin{matrix} 2ax=2by \\ 2cy=2dx+1 \end{matrix}\right. $$$$\left\{\begin{matrix} 2ax+x=2by \\ 2cy+y=2dx+1 \end{matrix}\right. $$$$\left\{\begin{matrix} 2ax=2by+y \\ 2cy=2dx+x+1 \end{matrix}\right. $$$$\left\{\begin{matrix} 2ax+x=2by+y \\ 2cy+y=2dx+x+1 \end{matrix}\right. $$

设 $k$ 是任意整数。

解第一个方程组得到 $2(ax-by)=0$ 且 $2(cy-dx)=1$。因为 $x,y$ 互质，所以 $(ax-by)$ 和 $(cy-dx)$ 都可以表示成任意整数。所有就有 $2k=0$ 且 $2k=1$，显然无解。

同理第二个方程组可以推出 $2k+x=0$ 且 $2k+y=1$，就是 $x$ 是偶数，$y$ 是奇数。

第三个方程组推出 $2k-y=0$ 且 $2k-x=1$，就是 $x$ 是奇数，$y$ 是偶数。

第四个方程组推出 $2k+x-y=0$ 且 $2k+y-x=1$，显然无解。

所以 $p(x,y)=1$ 当且仅当 $gcd(x,y)=1$ 且 $x+y$ 是一个奇数。

然后暴力求出所有的 $p(x,y)$ 即可，期望得分 $20pts$。

算法3：

如果 $x+y$ 是一个奇数那么 $x-y$ 也是一个奇数，所以 $gcd(x,x-y)=1$ 且 $x-y$ 是一个奇数也是 $p(x,y)=1$ 的充要条件。

定义 $w(x)$ 表示 $1\sim x$ 中有多少个奇数与 $x$ 互质，考虑如何计算 $w(x)$。

显然如果 $x$ 是一个偶数，那么没有偶数与它互质，即 $w(x)=\varphi(x)$，我们不难发现 $ans=\sum_{i=1}^{n}w(x)\times 2-2$。

如果 $x$ 是一个奇数，对于一个奇数 $k$，有 $gcd(x,k)=1$ 那么就有 $gcd(x,x-k)=1$ 也就是对于每个奇数与它互质那么一定有一个对应的偶数 $x-k$ 与它互质，也就是 $w(x)=\frac{\varphi(x)}{2}$，当然对于 $w(1)$ 需要进行特判。

那么显然线性求 $\varphi$ 就可以获得 $50pts$。

算法4：

显然答案就是奇数的 $\varphi$ 加上偶数的 $\varphi$ 除以 $2$。所以我们需要分开计算奇数和偶数的 $\varphi$

若 $n$ 是一个偶数，假设我们已经求出了 $p1=\sum_{i=1}^{n\div2}\varphi(x)$ （$x$ 是奇数）和 $p2=\sum_{i=1}^{n\div 2}\varphi(x)$（$x$ 是偶数）那么考虑如何求到 $n$。首先我们有 $\sum_{i=1}^n\varphi(x)$ （$x$ 是偶数）$=p1+p2\times 2$。（对于每个奇数乘上一个 $2$，根据 $\varphi$ 的定义我们发现它多了一个 $2$ 这个因子，而 $n$ 乘上了一个 $2$，所以 $\varphi$ 不变；而对于一个偶数乘上了一个 $2$，没有加减因子，但是 $n$ 乘上了一个 $2$，所以它的 $\varphi$ 也要乘 $2$）。

然后用杜教筛求出 $\sum_{i=1}^n \varphi(x)$ 然后减去前面求出的答案就是奇数的答案了。时间复杂度 $O(n^{\frac{2}{3}}\log n)$，预处理到 $1\sim 10^7$ 的答案即可大大缩小时间复杂度。

期望得分$100pts$。

算法5:

其实最终式子可以优化为递推式

$$ans(n)=ans(\lfloor \frac{n}{2}\rfloor)+\sum_{i=1}^n\varphi(i) $$

看到最终许多通过的选手都是写成这种形式的

$others$

对于$65$的部分分是给莫比乌斯反演的，没想到有人能优化到可以通过的形式。对于$ull$自然溢出需要注意的地方，就是在杜教筛中 $n\times (n+1)$ 时需要注意让偶数的那个先除以$2$否则会溢出之后再除上一个 $2$ 就会出现 $Wrong\ Answer$ 的情况。

然后还有人写到 $35$ 的部分分是我没有预料到的（因为我都不会写，果然选手的智慧是无限的）。

$code$

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#define ll unsigned long long
using namespace std;
const ll N=1e7+1;
ll T,n,cnt,mu[N],phi[N],pri[N];
ll sp1[N],sp2[N],p1[1100],p2[1100];
bool vis[N];
map<ll,ll> sp,sm; 
void prime(){
	phi[1]=1;
	for(ll i=2;i<N;i++){
		if(!vis[i])pri[++cnt]=i,phi[i]=i-1;
		for(ll j=1;j<=cnt&&pri[j]*i<N;j++){
			vis[pri[j]*i]=1;
			if(i%pri[j]==0){
				phi[i*pri[j]]=phi[i]*pri[j];
				break;
			}
			phi[i*pri[j]]=phi[pri[j]]*phi[i];
		}
	}
	for(ll i=1;i<N;i++){
		sp1[i]=sp1[i-1]+phi[i]*(i&1);
		sp2[i]=sp2[i-1]+phi[i]*(!(i&1));
	}
	return;
}
ll GetSphi(ll n){
	if(n<N)return sp1[n]+sp2[n];
	if(sp[n])return sp[n];
	ll rest=(n%2ull==0ull)?((ll)n/2ull*(n+1ull)):((ll)(n+1ull)/2ull*n);
	for(ll l=2ull,r;l<=n;l=r+1ull)
		r=n/(n/l),rest-=(r-l+1ull)*GetSphi(n/l);
	return (sp[n]=rest);
}
void dfs(ll x,ll n){
	p1[x]=p2[x]=0;
	if(n<N){
		p1[x]=sp1[n];
		p2[x]=sp2[n];
		return;
	}
	dfs(x+1,n/2);
	p2[x]+=p1[x+1]+p2[x+1]*2ull; 
	p1[x]+=GetSphi(n)-p2[x];
	return;
}
int main()
{
	prime();
	scanf("%llu",&T);
	while(T--){
		scanf("%llu",&n);dfs(0,n);
		printf("%llu\n",p1[0]+p2[0]*2ull-1ull);
	}
}