啥都不知道,被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卷积的理解