竭泽十分喜欢数论,并且在莫比乌斯反演点了很多奇怪的技能点
在介绍这个问题之前,竭泽会给大家介绍一点数论常识常见的数论符号和数论解题trick
表示i和j的最大公因数
- [n == 1] 这个符号表示,若n == 1, 则返回1, 否则返回0
(i)是莫比乌斯函数,
, 其中
为质因数
- 狄利克雷卷积 我们定义 * 为狄利克雷卷积符号, 那么
![]()
- 莫比乌斯反演
其中有一个重要性质![]()
前置知识一看就很简单,竭泽还想给大家看看经典的莫比乌斯反演的例子,就是运算下列式子
![]()
=![]()
=![]()
=![]()
=![]()
=![]()
=![]()
这里给出莫比乌斯线性筛的函数
const int maxn=1e6+5; bool vis[maxn]; int prime[maxn],mu[maxn]; void init_mu(int n){//init_mu(n) 就可得到1-n的莫比乌斯函数的值,存在mu中 int cnt=0; mu[1]=1; for(int i=2;i<n;i++){ if(!vis[i]){ prime[cnt++]=i; mu[i]=-1; } for(int j=0;j<cnt&&i*prime[j]<n;j++){ vis[i*prime[j]]=1; if(i%prime[j]==0) {mu[i*prime[j]]=0;break;} else { mu[i*prime[j]]=-mu[i];} } } }
使用这个函数之后,可以用这个函数存放莫比乌斯函数的值
介绍完了简单的例题,竭泽决定考考大家一个和上述例题非常相似的题目,看看大家是否都掌握了,是否都能举一反三,是否能看清事情的本质
竭泽定义了一个函数
...
竭泽再定义一个函数
现在竭泽给你两个数n, k,请求出
的值
因为答案可能非常大,请把答案对取模之后在输出
输入只有一行n, k
输出的值对
取模后的结果