首页 > 其他分享 >P4213 【模板】杜教筛(Sum)

P4213 【模板】杜教筛(Sum)

时间:2022-10-28 21:12:25浏览次数:110  
标签:lfloor right frac Sum 杜教 P4213 sum left

题目链接

P4213 【模板】杜教筛(Sum)

题目描述

给定一个正整数,求

\[ans_1=\sum_{i=1}^n\varphi(i) \]

\[ans_2=\sum_{i=1}^n \mu(i) \]

输入格式

本题单测试点内有多组数据

输入的第一行为一个整数,表示数据组数 \(T\)。

接下来 \(T\) 行,每行一个整数 \(n\),表示一组询问。

输出格式

对于每组询问,输出一行两个整数,分别代表 \(ans_1\) 和 \(ans_2\)。

样例 #1

样例输入 #1

6
1
2
8
13
30
2333

样例输出 #1

1 1
2 0
22 -2
58 -3
278 -3
1655470 2

提示

数据规模与约定

对于全部的测试点,保证 \(1 \leq T \leq 10\),\(1 \leq n \lt 2^{31}\)。

解题思路

杜教筛

杜教筛主要用来快速求解数论函数的前缀和问题,即对于这样一个数论函数 \(f(x)\),计算 \(S(n)=\sum_{i=1}^nf(i)\)
\(\color{red}{思考如何将原式转化为整除分块求解?}\)
设任意两个积性函数 \(f(x),g(x)\),由迪利克雷卷积,设 \(h(x)=f·g(x)\),则 \(\sum_{i=1}^n h(i)=\sum_{i=1}^n f·g(x)=\sum_{i=1}^n \sum_{d|i}^ig(d)f(\frac{i}{d})=\sum_{d=1}^ng(d)\sum_{d|i}^nf(\frac{i}{d})=\sum_{d=1}^ng(d)\sum_{i=1}^{\left \lfloor \frac{n}{d}\right \rfloor}f(i)=\sum_{d=1}^nS(\left \lfloor \frac{n}{d}\right\rfloor)\),则可以得到杜教筛公式:

\[g(1)S(n)=\sum_{i=1}^nh(i)-\sum_{i=2}^ng(i)S(\left \lfloor \frac{n}{i}\right \rfloor) \]

线性预处理前 \(O(n^{\frac{2}{3}})\) 个数,其复杂度为:

  • 时间复杂度:\(O(n^{\frac{2}{3}})\)

否则:

  • 时间复杂度:\(O(n^{\frac{3}{4}})\)

考虑本题:求解莫比乌斯前缀和,考虑元函数 \(\epsilon\) 作为迪利克雷卷积,由莫比乌斯函数的性质 \(\sum_{d|x}\mu(d)=\left\{\begin{matrix} \ 1 & ,x=1 \\\ 0 & ,x\neq 1 \end{matrix}\right.=\epsilon(x)\),即 \(\epsilon =\mu ·1\),则 \(S(n)=1-\sum_{i=1}^nS(\left \lfloor \frac{n}{i}\right \rfloor)\),此即莫比乌斯前缀和

求解欧拉函数前缀和,由欧拉函数性质:\(\sum_{d|n}\phi(d)=n\),同样地,令 \(h(x)=\phi(x)·1\),则 \(S(n)=\sum_{i=1}^n\phi(i)-\sum_{i=2}^nS(\left \lfloor \frac{n}{i}\right \rfloor)=\frac{n\times(n+1)}{2}-\sum_{i=2}^nS(\left \lfloor \frac{n}{i}\right \rfloor)\),此即欧拉函数的前缀和

  • 时间复杂度:\(O(n^{\frac{2}{3}})\)

代码

// Problem: P4213 【模板】杜教筛(Sum)
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4213
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// %%%Skyqwq
#include <bits/stdc++.h>
 
// #define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
 
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
 
template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
 
template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N=1e6+5;
int t,n,cnt,prime[N],v[N],u[N];
LL phi[N];
unordered_map<LL,int> mp_u;
unordered_map<int,LL> mp_phi;
void init(int n)
{
	u[1]=phi[1]=1;
	for(int i=2;i<=n;i++)
	{
		if(!v[i])
		{
			u[i]=-1;
			prime[++cnt]=v[i]=i;
			phi[i]=i-1;
		}
		for(int j=1;j<=cnt&&i*prime[j]<=n;j++)
		{
			if(v[i]<prime[j])break;
			if(i%prime[j]==0)u[i*prime[j]]=0;
			else
				u[i*prime[j]]=-u[i];
			v[i*prime[j]]=prime[j];
			phi[i*prime[j]]=(LL)phi[i]*(i%prime[j]?prime[j]-1:prime[j]);
		}
	}
	for(int i=1;i<=n;i++)u[i]+=u[i-1],phi[i]+=phi[i-1];
	
}
LL get(int a,LL b)
{
	return a/(a/b);
}
int ask_u(int x)
{
	if(x<N)return u[x];
	if(mp_u[x])return mp_u[x];
	int res=1;
	for(LL i=2,j;i<=x;i=j+1)
	{
		j=get(x,i); 
		res-=(LL)ask_u(x/i)*(j-i+1);
	}
	return mp_u[x]=res;
}
LL ask_phi(LL x)
{
	if(x<N)return phi[x];
	if(mp_phi[x])return mp_phi[x];
	LL res=x*(x+1)/2;
	for(LL i=2,j;i<=x;i=j+1)
	{
		j=get(x,i);
		res-=ask_phi(x/i)*(j-i+1);
	}
	return mp_phi[x]=res;
}
int main()
{
    init(N-1);
    for(scanf("%d",&t);t;t--)
    {
    	scanf("%d",&n);
    	printf("%lld %d\n",ask_phi(n),ask_u(n));
    }
    return 0;
}

标签:lfloor,right,frac,Sum,杜教,P4213,sum,left
From: https://www.cnblogs.com/zyyun/p/16837323.html

相关文章