题目描述
你有 $N$ 本书和一个 $K$ 层的书架。
随机地将 $N$ 本书放进书架，这个时候第 $i$ 层的书本数量为 $cnt_i$。
令 $f_i$ 为第 $i$ 个 $Fibonacci$ 数（$f_0=0, f_1=1, f_2=1, f_i=f_{i-1}+f_{i-2}$）。
令第 $i$ 层的美丽值 $beauty_i=2^{f_{cnt_i}}-1$，
则这个书架的总得分 $score=gcd(beauty_1, beauty_2, beauty_3, …, beauty_K)$。
现在给定 $N$ 和 $K$，求书架的得分的期望值。
输入和输出
输入
第一行是一个不超过 10 的正整数 $T$，代表有 $T$ 组测试数据。
接下来 $T$ 行，每行包含两个整数 $N, K$ （$0 < N, K leq 10^6$）。
输出
一共 $T$ 行。对于每一组数据，输出答案在模 $10^9+7$ 意义下的值。
样例
输入
1
6 8输出
797202805思路
我们知道, $gcd(x^a-1,x^b-1)=x^{gcd(a,b)}-1$ 。
所以我们就可以将 $gcd(beauty_1, beauty_2, beauty_3, …, beauty_k)$ 转化为 $2^{gcd(f_{cnt_1},f_{cnt_2},…,f_{cnt_k},)}-1$。
我们也可以轻易地证明 $gcd(f_x,f_y)=f_{gcd(x,y)}$。
所以我们最终得到了这个公式
$2^{f_{gcd(cnt_1,cnt_2,…,cnt_k}}-1$。
枚举每个可能的 $gcd$, 计算它的贡献。莫比乌斯反演即可。
首先，将 $N$ 分成 $K$ 个 $gcd$ 的倍数有 $C_{frac n{gcd}+k-1}^{k-1}$ 种方案，所以每个 $gcd$ 对答案的贡献为 $C_{frac n{gcd}+k-1}^{k-1} imes (2^{f_{gcd}}-1)$。
为了避免重复计算，使用莫比乌斯系数容斥。
没了。
代码
#include
#define maxn 2000010
#define mod 1000000007
#define ll long long
using namespace std;
int pri[maxn],top;
bool vis[maxn];
int mu[maxn],fib[maxn],k;
ll ny[maxn],jc[maxn];
ll ksm(ll a,ll b){
ll res=1;
while(b){
if (b&1) res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
void Init(int n){
ny[0]=jc[0]=fib[1]=mu[1]=1;
for (int i=2;i<=n;i++){
if (!vis[i]) pri[++top]=i,mu[i]=-1;
for (int j=1;j<=top&&i*pri[j]<=n;j++){
vis[i*pri[j]]=1;
if (i%pri[j]==0) break;
mu[i*pri[j]]=-mu[i];
}
}
for (int i=1;i<=n;i++)
jc[i]=jc[i-1]*i%mod;
ny[n]=ksm(jc[n],mod-2);
for (int i=n-1;i>=0;i--)
ny[i]=(ny[i+1]*(i+1))%mod;
for (int i=2;i<=n;i++)
fib[i]=(fib[i-1]+fib[i-2])%(mod-1);
}
ll C(int n,int m){
if (n==m||m==0) return 1;
return jc[n]*ny[m]%mod*ny[n-m]%mod;
}
ll cc(int n){
ll res=0;
for (int i=1;i<=n;i++)
if (n%i==0) res=(res+mu[i]*C(n/i+k-1,k-1)%mod+mod)%mod;
return res;
}
ll kk(int n){
return (ksm(2,fib[n])-1+mod)%mod;
}
int main(){
ios::sync_with_stdio(false);
Init(maxn-1);
int T;cin>>T;while(T--){
int n;
ll ans=0;
cin>>n>>k;
for (int i=1;i*i<=n;++i){
if (n%i==0){
ans=(ans+cc(n/i)*kk(i)%mod)%mod;
if (i*i!=n) ans=(ans+cc(i)*kk(n/i)%mod)%mod;
}
}
cout<