[hdu6434]Problem I. Count

题目大意：$T(T\leqslant 10^5)$组数据，每组数据给你$n(n\leqslant 2\times 10^7)$，求$\sum\limits_{i=1}^n\sum\limits_{j=1}^{i-1}[(i+j,i-j)==1]$

题解：
$$
\def\dsum{\displaystyle\sum\limits}
\begin{align*}
&\dsum_{i=1}^n\dsum_{j=1}^{i-1}[(i+j,i-j)=1]\\
&令k=i-j\\
=&\dsum_{i=1}^n\dsum_{k=1}^{i-1}[(2i-k,k)=1]\\
=&\dsum_{i=1}^n\dsum_{k=1}^{i-1}[(2i,k)=1]\\
\end{align*}
$$

$$
\therefore
(2i,k)=1\Rightarrow
\begin{cases}
(i,k)=1\\
(2,k)=1\\
\end{cases}\\
当i为偶数时：\\
(i,k)=1\\
\Rightarrow (2,k)=1\\
\therefore ans=\varphi(i)\\
当i为奇数时：\\
(2,k)=1\\
\Rightarrow k为奇数\\
\therefore k必为与i互质的数的奇数\\
\because (i,k)=1\Rightarrow(i,i-k)=1\\
\therefore 当i为奇数的时候，k奇偶各半\\
\therefore ans=\dfrac{\varphi(i)}2
$$

卡点：无

C++ Code：

#include <cstdio>

#define maxn 20000010

int Tim, n;

long long pre[maxn];

int plist[maxn << 3], pt, phi[maxn];

bool isp[maxn];

void sieve(int n) {

	phi[1] = 1;

	pre[1] = 0;

	isp[1] = true;

	for (int i = 2; i < n; i++) {

		if (!isp[i]) {

			plist[pt++] = i;

			phi[i] = i - 1;

		}

		for (int j = 0; j < pt && i * plist[j] < n; j++) {

			int tmp = i * plist[j];

			isp[tmp] = true;

			if (i % plist[j] == 0) {

				phi[tmp] = phi[i] * plist[j];

				break;

			}

			phi[tmp] = phi[i] * phi[plist[j]];

		}

		pre[i] = pre[i - 1] + ((i & 1) ? phi[i] / 1 : phi[i]);

	}

}

int main() {

	sieve(maxn);

	scanf("%d", &Tim);

	while (Tim --> 0) {

		scanf("%d", &n);

		printf("%lld\n", pre[n]);

	}

	return 0;

}

巴特西

[hdu6434]Problem I. Count

最新文章

热门文章