【2018 HDU 多校 Contest 6 / 6363】Bookshelf / 题解

题目描述

你有 $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;" (i%pri[j]="=0)" break; mu[i*pri[j]]="-mu[i];" } i="1;i<=n;i++)" jc[i]="jc[i-1]*i%mod;" ny[n]="ksm(jc[n],mod-2);">=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; jc[n]*ny[m]%mod*ny[n-m]%mod; cc(int n){ res="0;" for (int i="1;i<=n;i++)" (n%i="=0)" res; kk(int (ksm(2,fib[n])-1+mod)%mod; int main(){ ios::sync_with_stdio(false); init(maxn-1); 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;" (i*i!="n)" } cout<