Solution -「LGR-087」「洛谷 P6860」象棋与马 (mathcal{Description}) (mathcal{Solution})
Link.
在一个 (mathbb R^2) 的 ((0,0)) 处有一颗棋子，对于参数 (a,b)，若它当前坐标为 ((x,y))，则它下一步可以走到 ((xpm a,ypm b)) 和 ((xpm b,ypm a))。令 (p(s,t)) 表示 (a=s,b=t) 时，棋子是否能走遍所有整点。求：
[sum_{i=1}^nsum_{j=1}^np(a,b)
]
答案自然溢出。
(T) 组数据，(nTle10^{11})。
(mathcal{Solution})
首先来描述 (p(s,t))，运用“组合操作”的思想，一颗棋子能走到所有整点，当且仅当它能位移 ((pm 1,0)) 和 ((0,pm 1))。结合样例想一下发现 (p(s,t)=[2 ot|(s+t)landgcd(s,t)=1])。于是问题等价于求 (n) 以内奇偶性不同且互素的数对个数。推式子：
[egin{aligned}
sum_{i=1}^nsum_{j=1}^n[2
ot|(s+t)landgcd(s,t)=1]&=sum_{i=1}^nsum_{j=1}^n[gcd(i,j)=1]-sum_{i=1}^nsum_{j=1}^n[2
ot|i][2
ot|j][gcd(i,j)=1]\
&=sum_{d=1}^nmu(d)lfloorfrac{n}{d}
floor^2-sum_{d=1}^n[2
ot|d]mu(d)lceilfrac{n}{d}
ceil^2
end{aligned}
]
所以问题在于求：
[sum_{i=1}^n[2|i]mu(i)=-sum_{i=1}^{lfloorfrac{n}2
floor}mu(i)+sum_{i=1}^{lfloorfrac{n}2
floor}[2|n]mu(i)
]
利用 (mu) 积性，(2) 与奇数互素可以化成后面的样子，前一项杜教筛，后一项递归到规模小一半的原问题，记忆化一下直接计算即可。
复杂度 (mathcal O(n^{frac{2}3}))（？
(mathcal{Code})
求奇偶 (mu) 的函数写得有点丑，知道意思就行 owo。
/* Clearink */
#include <cstdio>
#include <tr1/unordered_map>
typedef unsigned long long ULL;
const int MAXN = 7e6;
ULL n;
int pn, pr[MAXN + 5], mu[MAXN + 5], mus[MAXN + 5], emus[MAXN + 5];
bool vis[MAXN + 5];
std::tr1::unordered_map<ULL, ULL> remmu, rememu;
inline void sieve ( const int n ) {
mu[1] = mus[1]= 1;
for ( int i = 2; i <= n; ++ i ) {
if ( ! vis[i] ) pr[++ pn] = i, mu[i] = -1;
for ( int j = 1, t; j <= pn && ( t = i * pr[j] ) <= n; ++ j ) {
vis[t] = true;
if ( !( i % pr[j] ) ) break;
mu[t] = -mu[i];
}
mus[i] = mus[i - 1] + mu[i];
emus[i] = emus[i - 1] + !( i & 1 ) * mu[i];
}
}
inline ULL calcMus ( const ULL n ) {
if ( n <= MAXN ) return mus[n];
if ( remmu.count ( n ) ) return remmu[n];
ULL ret = 1;
for ( ULL l = 2, r; l <= n; l = r + 1 ) {
r = n / ( n / l );
ret -= ULL ( r - l + 1 ) * calcMus ( n / l );
}
return remmu[n] = ret;
}
inline ULL calcEvenMus ( const ULL n ) {
if ( n <= MAXN ) return emus[n];
if ( rememu.count ( n ) ) return rememu[n];
return rememu[n] = calcEvenMus ( n >> 1 ) - calcMus ( n >> 1 );
}
inline ULL calcOddMus ( const ULL n ) {
return calcMus ( n ) - calcEvenMus ( n );
}
int main () {
sieve ( MAXN );
int T;
for ( scanf ( "%d", &T ); T --; ) {
scanf ( "%llu", &n ); ULL ans = 0;
for ( ULL l = 1, r; l <= n; l = r + 1 ) {
r = n / ( n / l );
ans += ( calcMus ( r ) - calcMus ( l - 1 ) ) * ( n / l ) * ( n / l );
ans -= ( calcOddMus ( r ) - calcOddMus ( l - 1 ) )
* ( n / l + 1 >> 1 ) * ( n / l + 1 >> 1 );
}
printf ( "%llu
", ans );
}
return 0;
}