题目
题目链接：https://www.luogu.com.cn/problem/P6860
Amazing John 有一个无限大的棋盘来下马棋。
有一个马最开始在 ((0,0))，它的每一步可以走一个 (a imes b) 的矩形（ 即能够从((x,y))到达 ((xpm a,ypm b)) 或 ((xpm b,ypm a)) ）。
若马通过上述移动方式可以到达棋盘中任意一个点，那么 (p(a,b)=1)，否则 (p(a,b)=0)。
现在 Amazing John 给你 (T) 组询问，每组询问他会给出一个正整数 (n)，他想知道
的值。
思路
显然马可以走到任意点的充要条件就是可以走到 ((1,0))。我们可以列出马可以走到的点的集合，容易得出它可以走到 ((1,0)) 的充要条件是 (gcd(a,b)=1) 且 (a+b) 是奇数。这个条件等价于 (gcd(a,b)=1) 且 (a-b) 是奇数。
如果 (a) 是偶数，那么显然任意小于 (a) 且与 (a) 互质的数都满足 (a-b) 是奇数，所以此时合法的 (b) 的数量就是 (varphi(a))。
如果 (a) 是奇数，如果 (gcd(a,b)=1)，那么 (gcd(a-b)) 显然也是 (1)，而 (b) 与 (a-b) 中恰好是一奇一偶，所以任意一个与 (a) 互质的奇数都对应一个与 (a) 互质的偶数，所以此时合法的 (b) 的数量是 (frac{varphi(a)}{2})。
所以答案就是
要乘二的原因是对于 (p(a,b)) 和 (p(b,a)) 两组合法解，我们只计算了其中一种（也就是 (a>b) 那种）。而减一则是因为 (p(1,1)) 被计算了，要舍去。
考虑怎么计算上述式子。假设我们已经求出了 ([1,n]) 中，偶数的 (varphi) 和奇数的 (varphi) 各自的和，我们需要将它扩展到 ([1,2n])。
对于任意的奇数 (x)，它乘二之后会变成偶数。假设原来 (varphi(x)=x imes frac{p_1-1}{p_1} imes frac{p_2-1}{p_2}cdots)，由于 (2) 是一个 (x) 之前没有的因子，所以 (varphi(2x)=2x imes frac{p_1-1}{p_1} imes frac{p_2-1}{p_2}cdots imes frac{1}{2})，依然等于 (varphi(x))。
对于任意的偶数 (x)，它乘二之后并没有多出任何之前不存在的质因子，所以 (varphi(2x)=2x imes frac{p_1-1}{p_1} imes frac{p_2-1}{p_2}cdots=2varphi(x))。
所以 ([1,2n]) 中偶数的 (varphi) 之和等于 (s_{odd}+2s_{even})。
然后我们用杜教筛求出 ([1,2n]) 所有数的 (varphi) 之和，用该值减去偶数的 (varphi) 之和就得到了奇数的 (varphi) 之和。再回溯计算即可。
时间复杂度 (O(Tn^{frac{2}{3}}log n))。
代码
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N=1e7+10;
int Q,m,prm[N];
ull n,s1,s2,phi[N];
bool v[N];
map<int,ull> sphi;
void findprm(int n)
{
phi[1]=1;
for (int i=2;i<=n;i++)
{
if (!v[i]) prm[++m]=i,phi[i]=i-1;
for (int j=1;j<=m;j++)
{
if (i>n/prm[j]) break;
v[i*prm[j]]=1; phi[i*prm[j]]=phi[i]*(prm[j]-1);
if (i%prm[j]==0)
{
phi[i*prm[j]]=phi[i]*prm[j];
break;
}
}
}
}
ull sumphi(ull n)
{
if (n<N) return phi[n];
if (sphi[n]) return sphi[n];
ull res=114514;
if (n&1ULL) res=(n+1ULL)/2ULL*n;
else res=n/2ULL*(n+1ULL);
for (ull l=2,r;l<=n;l=r+1)
{
r=n/(n/l);
res-=sumphi(n/l)*(r-l+1);
}
return sphi[n]=res;
}
void calc(ull n,ull &s1,ull &s2)
{
if (n==1)
{
s1=1; s2=0;
return;
}
calc(n/2ULL,s1,s2);
s2=s1+s2*2ULL; s1=sumphi(n)-s2;
}
int main()
{
findprm(N-1);
for (int i=1;i<N;i++)
phi[i]=phi[i-1]+phi[i];
scanf("%d",&Q);
while (Q--)
{
cin>>n;
calc(n,s1,s2);
cout<<s1+s2*2ULL-1ULL<<endl;
}
return 0;
}