有点复杂的gcd问题
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

竭泽十分喜欢数论,并且在莫比乌斯反演点了很多奇怪的技能点

在介绍这个问题之前,竭泽会给大家介绍一点数论常识常见的数论符号和数论解题trick

  1. 表示i和j的最大公因数
  2. [n == 1] 这个符号表示,若n == 1, 则返回1, 否则返回0
  3. (i)是莫比乌斯函数,, 其中为质因数
  4. 狄利克雷卷积 我们定义 * 为狄利克雷卷积符号, 那么
  5. 莫比乌斯反演
    其中有一个重要性质

前置知识一看就很简单,竭泽还想给大家看看经典的莫比乌斯反演的例子,就是运算下列式子



这时候如果我们直接遍历肯定会TLE,那么试试神奇的莫比乌斯反演,在这之前,我们先整理一下式子


我们同时除以k,得到


这时候我们发现[gcd(i, j) == 1]很像[n == 1],这时候想到

于是我们尝试着枚举一个新的数字d,使得d|gcd(i, j),从而得到


其实我们很轻易的就可以知道d的枚举范围其实是[1, n/k ], 那么这个式子就可以改写成


我们更换一下顺序


我们看到,换成人话就是说 n/k 里面有多少个是d的倍数,那其实很轻易知道这个式子的值是,(比如说10里面有多少个3的倍数当然是10/3啦)

所以式子可以写为


这样就不会超时了

整理一下过程


=

=

=

=

=

=

这里给出莫比乌斯线性筛的函数

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

输出描述:

输出g(a_1, a_2, a_3, . . ., a_k)的值对取模后的结果
示例1

输入

复制
185626 15

输出

复制
228598632

备注: