【bzoj4804】欧拉心算欧拉函数

题目描述

给出一个数字N

输入

第一行为一个正整数T，表示数据组数。

接下来T行为询问，每行包含一个正整数N。

T<=5000,N<=10^7

输出

按读入顺序输出答案。

样例输入

1
10

样例输出

136

题解

欧拉函数

其中用到了$\sum\limits_{i=1}^k\sum\limits_{j=1}^k[\gcd(i,j)=1]=2\sum\limits_{i=1}^k\varphi(i)-1$

这个推导很简单：由欧拉函数的定义，$\sum\limits_{i=1}^k\sum\limits_{j=1}^i[\gcd(i,j)=1]=\sum\limits_{i=1}^k\varphi(i)$，此时$i\ge j$，而当$i\le j$时情况相同。最后减掉重复计算的(1,1)即为左边。

然后剩下的就好说了，预处理欧拉函数$\varphi$和其前缀和$sum$，分块枚举$\lfloor\frac nd\rfloor$的取值并计算即可。

#include <cstdio>

#include <algorithm>

using namespace std;

#define N 10000010

typedef long long ll;

const int m = 10000000;

int prime[N] , tot , phi[N];

ll sum[N];

bool np[N];

int main()

{

	int i , j , t , n , last;

	ll ans;

	sum[1] = phi[1] = 1;

	for(i = 2 ; i <= m ; i ++ )

	{

		if(!np[i]) phi[i] = i - 1 , prime[++tot] = i;

		for(j = 1 ; j <= tot && i * prime[j] <= m ; j ++ )

		{

			np[i * prime[j]] = 1;

			if(i % prime[j] == 0)

			{

				phi[i * prime[j]] = phi[i] * prime[j];

				break;

			}

			else phi[i * prime[j]] = phi[i] * (prime[j] - 1);

		}

		sum[i] = sum[i - 1] + phi[i];

	}

	scanf("%d" , &t);

	while(t -- )

	{

		scanf("%d" , &n) , ans = 0;

		for(i = 1 ; i <= n ; i = last + 1) last = n / (n / i) , ans += (sum[last] - sum[i - 1]) * sum[n / i];

		printf("%lld\n" , 2 * ans - sum[n]);

	}

	return 0;

}

巴特西

【bzoj4804】欧拉心算欧拉函数

最新文章

热门文章

巴特西

【bzoj4804】欧拉心算 欧拉函数

最新文章

热门文章

【bzoj4804】欧拉心算欧拉函数