浅谈狄利克雷相关题目套路

啥都不知道,被yyc D爆了/kk

扔道题
P2714 四元组统计
乍一看,就想推式子,结果发现自己是个憨批

莫反就两条式子
浅谈狄利克雷相关题目套路
浅谈狄利克雷相关题目套路

考虑第二种
设 f ( n ) 表 示 四 元 组 n ∣ gcd ⁡ 的 个 数 \large 设f(n)表示四元组n|\gcd的个数 设f(n)表示四元组n∣gcd的个数

设 g ( n ) 表 示 四 元 组 gcd ⁡ = n 的 个 数 \large 设g(n)表示四元组\gcd=n的个数 设g(n)表示四元组gcd=n的个数

发现刚好可以用第二条式子

于是这题就做完了

再来看看这题
P5495 Dirichlet 前缀和
考虑每一个每一个质数都是一维
这题就相当于是做了一个高维前缀和(卷 I I I)
代码就类似FMT那么写就好了
code:

	for(int j = 1; j <= sz; j ++)
		for(int i = 1; i * prime[j] <= n; i ++)
			a[i * prime[j]] += a[i];

瞬间加深了对dirichlet卷积的理解

上一篇:欧拉回路学习笔记


下一篇:一文解读什么是 LeSS(Large Scale Scrum)