本来是考试的,但是数论忘了,只好滚去学数论。
性质
若 f(x) 和 g(x) 均为积性函数,则以下函数也为积性函数:
h(x)h(x)h(x)h(x)=f(xp)=fp(x)=f(x)g(x)=d∣x∑f(d)g(dx)
设 x=∏piki
若 F(x) 为积性函数,则有 F(x)=∏F(piki) 。
若 F(x) 为完全积性函数,则有 F(X)=∏F(pi)ki 。
例子
- 单位函数: ϵ(n)=[n=1] (完全积性)
- 恒等函数: idk(n)=nk id1(n) 通常简记作 id(n) 。(完全积性)
- 常数函数: 1(n)=1 (完全积性)
- 除数函数: σk(n)=∑d∣ndk σ0(n) 通常简记作 d(n) 或 τ(n) , σ1(n) 通常简记作 σ(n) 。
- 欧拉函数: φ(n)=∑i=1n[gcd(i,n)=1]
- 莫比乌斯函数: μ(n)=⎩⎨⎧10(−1)ω(n)n=1∃d>1:d2∣notherwise ,其中 ω(n) 表示 n 的本质不同质因子个数,它是一个加性函数。
文章作者: Cauphenuny
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 Cauphenuny's Blog!
相关推荐
2020-12-03
树的重心相关结论
转载:pyqpyq...
2021-05-30
min-25 筛
zxy 讲题的时候顺便讲了一下 min-25 筛可以解决一种函数前缀和,
2021-03-23
多项式部分运算
乘法 NTT 构造模意义单位根。 发现 δpgk=(p−1)gcd(k,p−1)\delta_pg^k=\dfrac{(p-1)}{\gcd(k, p -1)}δpgk=gcd(k,p−1)(p−1),当 n∣(p−1)n|(p-1)n∣(p−1) 时, δpg(p−1)/n=(p−1)gcd(p−1n,p−1)=n\delta_pg^{(p-1)/n}=\dfrac{(p-1)}{\gcd(\frac{p-1}{n}, p-1)}=nδpg(p−1)/n=gcd(np−1,p−1)(p−1)=n 令 ωn=g(p−1)/n\omega_n=g^{(p-1)/n}ωn=g(p−1)/n ,则 ωn0,ωn1,⋯ ,ωnn−1\omega_n^0,\omega_n^1,\cdots,\omega_n^{n-1}ωn0,ωn1,⋯,ωnn−1...
2021-04-17
HNOI2021总结
总结 Day1 开考先看看三个题,发现 T2 是个构造,T3 不像是会做的题目,然后就开始想第一题。 正好昨天看了一眼 wqs 二分,这个题目也有一个只能选 kkk 个的限制,于是思路逐渐跑偏,也把模型转换了一下,大概就花了一两个小时的时间,然后发现我不太会做没有限制 kkk 个的情况,但是我还是觉得只是自己最后一步思考得不够深入,画了一堆图,就一直想,甚至把手推 wqs 二分,把昨天没看懂的部分想明白了,最后还是放弃了这个思路,然后很快就想出了一个二分加双指针的做法,也没有什么细节,很快就码完了,但是调了一小会儿,过了几个样例然后就已经十一点半还是十二点了。 接着赶紧看第二题,没有什么思路,再加上把题目想的复杂了一点,觉得这种限制很难跑,就先写了高斯消元,但是我已经半年没写过高斯消元了,调了一个小时,然后发现这个做法假掉了,赶紧上了一个随机化,在 12:58 的时候过了样例,第三题就没有看。 最终分数:90+0+090+0+090+0+0 ,T1 被卡常了,T2 没搞到分 总结一下 Day1 的失误主要是 T1...
2020-10-03
可持久化平衡树
link fhq 改几个函数就可以了 12345int refresh(int id) { tot++; p[tot] = p[id]; return tot;} 123456789101112131415void split_by_val(int rt, int &a, int &b, int val) { if (rt == 0) { a = b = 0; return; } if (p[rt].val <= val) { a = refresh(rt);// split_by_val(p[rt].rs, p[a].rs, b, val); pushup(a);//记得是pushup(a),不是pushup(rt)!!! } else { b = refresh(rt);// split_by_val(p[rt].ls, a,...
2021-02-06
P5851 (USACO19DEC) Greedy Pie Eaters P
区间 dp ,注意枚举端点 i,j,k 的顺序,模拟一下就好了,如果使用了未更新的状态,就是错的 sorry for that i don’t have a chinese input method Functions: g(x, l, r) means we have the largest cow which can eat pos(x) , and it can only affect pies in [l, r] f(x, l, r) means the weight summary that we can get from a sequence of cows, and it only affect pies in [l, r] So we have the things below: 12345678910111213foreach cow_i foreach x in range[l_i, r_i] g(x, l_i, r_i) = w_i;foreach k in [1 -> n] foreach i in [k -> 1], j in [k...
评论