莫比乌斯

原题链接题意\(T\)组询问，每次询问求：\[\sum_{i=1}^{n}\sum_{i=1}^{m}[\gcd(i,j)\inprime]\]\(T=10^4,n,m\leq10^7\)。思路不难想到枚举质数，将原式化简为：\[\sum......

大家好，我不会数学实锤了。文章内容较杂，分章节叙述了的大部分有关内容。为什么把这俩放一起？我不知道。积性函数积性函数：\(\foralla,b\)，\(a\perpb\)，如果一个函数\(f\)......

引入考虑一个基本问题：给定序列\(a_n,b_n\)，求出序列\(c_n\)，满足\(c_i=\sum_{j\oplusk=i}a_jb_k\)，其中\(\oplus\)是一种二元运算符，形如上式的问题一般被称为卷积。......

题面设为的约数个数，给定，求题目分析有这样一个结论这道题就是下面这道题的数据增强版,那么这个结论的证明就不再赘述,请自行查看下面的(蒟蒻)博客​​传送门:[SDOI2015][bz......

题目描述求题目分析乍一看十分像裸莫比乌斯反演,然而的范围让人望而却步于是先变化一下式子枚举令k=Td则此时可以整除分块优化,每次算出相等的上下界后用莫比乌斯反演计......

题目描述有求只有最多组数据题目分析如此一来就可以杜教筛了,然而仅仅这样还是会T,于是我们在想一想如何筛出前面一部分的值令,根据莫比乌斯反演于是用筛出前项就行了......

题目描述组数据,给出,,求题目分析直接开始变换,假设N<M总算推完了…此时只需要线性筛出,然后处理的前缀和而可以出利用整除分块优化,时间复杂度为ACcode([bzoj2693]j......

题目描述给出表示一个的格点图,求能够互相看见的点对个数对取模的值.能互相看见定义为此两点连线上没有其他的格点且欧氏距离在[l,r]范围内题目分析首先我们将上下左右相邻......

莫比乌斯反演与杜教筛积性函数定义对于一个数论函数\(f\)，若满足\(\forall(a,b)=1\)都有\(f(ab)=f(a)f(b)\)，那么称\(f\)为积性函数。例子常见的积性函数有很多，......

零，前言主要内容及顺序：积性函数→几种常见积性函数→狄利克雷卷积→莫比乌斯反演→狄利克雷前缀和所有性质/结论都有证明，请放心食用。本文中，变量\(p\)的取值范......