\(\mathcal{Description}\)

Link.

在一个 \(\mathbb R^2\) 的 \((0,0)\) 处有一颗棋子，对于参数 \(a,b\)，若它当前坐标为 \((x,y)\)，则它下一步可以走到 \((x\pm a,y\pm b)\) 和 \((x\pm b,y\pm a)\)。令 \(p(s,t)\) 表示 \(a=s,b=t\) 时，棋子是否能走遍所有整点。求：

\[\sum_{i=1}^n\sum_{j=1}^np(a,b)
\]

答案自然溢出。

\(T\) 组数据，\(nT\le10^{11}\)。

\(\mathcal{Solution}\)

首先来描述 \(p(s,t)\)，运用“组合操作”的思想，一颗棋子能走到所有整点，当且仅当它能位移 \((\pm 1,0)\) 和 \((0,\pm 1)\)。结合样例想一下发现 \(p(s,t)=[2\not|(s+t)\land\gcd(s,t)=1]\)。于是问题等价于求 \(n\) 以内奇偶性不同且互素的数对个数。推式子：

\[\begin{aligned}
\sum_{i=1}^n\sum_{j=1}^n[2\not|(s+t)\land\gcd(s,t)=1]&=\sum_{i=1}^n\sum_{j=1}^n[\gcd(i,j)=1]-\sum_{i=1}^n\sum_{j=1}^n[2\not|i][2\not|j][\gcd(i,j)=1]\\
&=\sum_{d=1}^n\mu(d)\lfloor\frac{n}{d}\rfloor^2-\sum_{d=1}^n[2\not|d]\mu(d)\lceil\frac{n}{d}\rceil^2
\end{aligned}
\]

所以问题在于求：

\[\sum_{i=1}^n[2|i]\mu(i)=-\sum_{i=1}^{\lfloor\frac{n}2\rfloor}\mu(i)+\sum_{i=1}^{\lfloor\frac{n}2\rfloor}[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\n", ans );

	}

	return 0;

}

巴特西

Solution -「LGR-087」「洛谷 P6860」象棋与马

\(\mathcal{Description}\)

\(\mathcal{Solution}\)

\(\mathcal{Code}\)

最新文章

热门文章