解题报告

重新看一遍发现这题十分斯波……我们要求的是：

$$ \sum_{\{a_k\}}e[(a_1,a_2,\cdots,a_k)]\\ \sum_{\{a_k\}}\sum_{d|(a_1,a_2,\cdots,a_k)}\mu(d)\\ \sum_{d=1}^{n}\mu(d)\sum_{\{a_k\}}[d|(a_1,a_2,\cdots,a_k)]\\ \sum_{d=1}^{n}\mu(d){\lfloor{n\over d}\rfloor+k-1\choose k-1} $$

后面那个组合数表示可重复选取 $k$ 个元素的方案数，可以每次 $O(k)$ 求，再用杜教筛求 $\mu​$ 的前缀和，就可以除法分块了。Manchery表示杜教筛套上除法分块复杂度不变（证明？我当然不会），所以就不虚了……

示例程序

因为多组数据，复杂度还是GG了，所以再预处理组合数前 $10^6$ 就行了QAQ。

#include<map>
#include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=1000000,MOD=1e9+7;

int te,n,K,sum[maxn+5],p[maxn+5],fac[maxn+5],INV[maxn+5],ans;bool pri[maxn+5];map<int,int> F;

inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
inline void Make(int n){
    INV[1]=INV[0]=1;for (int i=2;i<=n;i++) INV[i]=(LL)(MOD-MOD/i)*INV[MOD%i]%MOD;
    fac[0]=1;for (int i=1;i<=n;i++) fac[i]=(LL)fac[i-1]*i%MOD,INV[i]=(LL)INV[i-1]*INV[i]%MOD;
    for (int i=(sum[1]=1,2);i<=n;i++){
        if (!pri[i]) p[++p[0]]=i,sum[i]=MOD-1;
        for (int j=1,t;j<=p[0]&&(t=i*p[j])<=n;j++)
            if (pri[t]=true,i%p[j]) sum[t]=(MOD-sum[i])%MOD; else {sum[t]=0;break;}
    }for (int i=1;i<=n;i++) AMOD(sum[i],sum[i-1]);
}
int Sum(int n){
    if (n<=maxn) return sum[n];if (F.count(n)) return F[n];int ans=1;
    for (int l=2,r;l<=n;l=r+1) r=n/(n/l),AMOD(ans,MOD-(LL)(r-l+1)*Sum(n/l)%MOD);return F[n]=ans;
}
inline int C(int n,int k){
    if (n<=maxn) return (LL)fac[n]*INV[k]%MOD*INV[n-k]%MOD;
    int ans=INV[k];for (int i=0;i<k;i++) ans=(LL)ans*(n-i)%MOD;return ans;
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    for (Make(maxn),scanf("%d",&te);te;te--){
        scanf("%d%d",&n,&K);ans=0;
        for (int l=1,r;l<=n;l=r+1)
            r=n/(n/l),AMOD(ans,(LL)(Sum(r)+MOD-Sum(l-1))*C(n/l+K-1,K)%MOD);
        printf("%d\n",ans);
    }return 0;
}