CF976-F. Count Leaves-min25筛（红温了）

link：https://codeforces.com/contest/2020/problem/F
题意：给定 \(n,d,k\)，用如下方式构造树\(T_{n,d}\)：

• 树的根是一个标有数字 \(n\) 的节点。这是树的第 \(0\) 层。
• 对于从 \(0\) 到 \(d−1\) 的每个 \(i\) ，对于第 \(i\) 层的每个顶点，执行以下操作：如果当前顶点标记为 \(x\) ，创建其子顶点并标记为 \(x\) 的所有可能的不同因此 。这些子顶点将位于 \((i+1)\) 层。
• \(d\) 层上的顶点就是树的叶子。
  \(f(n,d)\) 表示 \(T_{n,d}\) 的叶子结点个数，求 \(\sum_{i=1}^n f(i^k,d)\)，\(1\leq n\leq 10^9,1\leq k,d\leq 10^5\).

---

（喜欢赛后过题）

显然 \(f(n,d)\) 对于固定的 \(d\)，是关于 \(n\) 的积性函数（相当于一直做Dirichlet前缀和），考虑 \(f(p^q,d)\)，每一层往下相当于做一个前缀和，答案是 \(\frac{1}{(1-x)^{q+1}}\) 中 \([x^d]\) 的系数，广义二项式定理展开是 \(\binom{d+q}{d}\)，那么对于 \(f(p^{kq},d)\) 就是 \(\binom{kq+d}{d}\)，那么现在要求这个东西的前缀和，感觉没什么好的办法，直接上一个min25筛：

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
constexpr int MOD=1e9+7;
constexpr int N=3e6+5;
int ksm(int a,int b){int ret=1;a%=MOD;for(;b;b>>=1,a=(ll)a*a%MOD)if(b&1)ret=(ll)ret*a%MOD;return ret;
}
int inv(int x){return ksm(x,MOD-2);}
int fact[N],inv_fact[N];
void init(){fact[0]=1;rep(i,1,N-1)fact[i]=(ll)fact[i-1]*i%MOD;inv_fact[N-1]=inv(fact[N-1]);for(int i=N-1;i>=1;i--)inv_fact[i-1]=(ll)inv_fact[i]*i%MOD;
}
int C(int n,int k){if(k>n)return 0;return (ll)fact[n]*inv_fact[k]%MOD*inv_fact[n-k]%MOD;
}
namespace Min25{  constexpr int maxs=2e5;void add(int &x,const int & y){x+=y;if(x>=MOD)x-=MOD;}void dec(int &x,const int & y){x+=MOD-y;if(x>=MOD)x-=MOD;}int sum(const int &x,const int & y){return x+y<MOD?x+y:(x+y-MOD);}int sub(const int &x,const int & y){return x<y?x+MOD-y:x-y;}template<typename T>long long sqrll(const T&x){return (ll)x*x;}long long global_n,lis[maxs + 1];int K,d;int pri[maxs / 7], lpf[maxs + 1], spri[maxs + 1],pcnt,lim,cnt;int le[maxs + 1],ge[maxs + 1];//x<=sqrt(n),x>sqrt(n)int G[maxs + 1][2], Fprime[maxs + 1];#define idx(v) (v <= lim ? le[v] : ge[global_n / v])void sieve(const int &n) {rep(i,2,n){if(!lpf[i]){lpf[i]=++pcnt;pri[lpf[i]]=i;spri[pcnt]=sum(spri[pcnt-1],1);//}for(int j=1,v;j<=lpf[i];j++){v=i*pri[j];if(v>n)break;lpf[v]=j;}}}void init(const int &n,int _k,int _d){//calc Fprimeglobal_n=n;K=_k;d=_d;cnt=0;for(ll i=1,j,v;i<=n;i=n/j+1){j=n/i;v=j%MOD;lis[++cnt]=j;(j<=lim?le[j]:ge[n/j])=cnt;G[cnt][0]=sub(v,1ll);//}rep(k,1,pcnt){const int p=pri[k];const ll sqrp=sqrll(p);for(int i=1;lis[i]>=sqrp;i++){const ll v=lis[i]/p;const int id=idx(v);dec(G[i][0],sub(G[id][0],k-1));}}rep(i,1,cnt)Fprime[i]=(ll)G[i][0]*C(K+d,d)%MOD;//}int fp(const int &p,const int &c){return C(c*K+d,d);}//int F(const int &k,const ll &n){if(pri[k]>n||n<=1)return 0;const int id=idx(n);int ans=sub(Fprime[id],(ll)spri[k-1]*C(K+d,d)%MOD);//for(int i=k;i<=pcnt&&sqrll(pri[i])<=n;i++){long long pw=pri[i],pw2=sqrll(pw);for(int c=1;pw2<=n;c++,pw=pw2,pw2*=pri[i])add(ans,((ll)fp(pri[i],c)*F(i+1,n/pw)+fp(pri[i],c+1))%MOD);}return ans;}
}int main(){fastio;int tc;cin>>tc;init();Min25::lim=sqrt(1e9);Min25::sieve(Min25::lim+1000);while(tc--){int n,k,d;cin>>n>>k>>d;Min25::init(n,k,d);cout<<(Min25::F(1,n)+1)%MOD<<endl;}return 0;
}