bookshelf

Problem Description

Patrick Star bought a bookshelf, he named it ZYG !!

Patrick Star has N book .

The ZYG has K layers (count from 1 to K) and there is no limit on the capacity of each layer !

Now Patrick want to put all N books on ZYG :

1. Assume that the i-th layer has cnti(0≤cnti≤N) books finally.
2. Assume that f[i] is the i-th fibonacci number (f[0]=0,f[1]=1,f[2]=1,f[i]=f[i−2]+f[i−1]).
3. Define the stable value of i-th layers stablei=f[cnti].
4. Define the beauty value of i-th layers beautyi=2stablei−1.
5. Define the whole beauty value of ZYG score=gcd(beauty1,beauty2,...,beautyk)(Note: gcd(0,x)=x).

Patrick Star wants to know the expected value of score if Patrick choose a distribute method randomly !

Input

The first line contain a integer T (no morn than 10), the following is T test case, for each test case :

Each line contains contains three integer n,k$(0<n,k\le10^{6}).$

Output

For each test case, output the answer as a value of a rational number modulo $10^{9}+7.$.

Formally, it is guaranteed that under given constraints the probability is always a rational number pq (p and q are integer and coprime, q is positive), such that q is not divisible by 109+7. Output such integer a between 0 and $10^{9}+6.$ that p−aq is divisible by $10^{9}+7.$

Sample Input

1 6 8

Sample Output

797202805

$$\large gcd(fib[a],fib[b])=fib[gcd(a,b)]$$

$$\Large C^{K-1}_{\frac{N}{g}+K-1}$$

$$f[g]=F[g]-F[2g]-F[3g]-F[5g]+F[6g]……F[N]$$

$$\large f[g] = \sum_{g|d\&d|N}\mu{(\frac{d}{g})}F[d]$$

$$\Large F[g]= C^{K-1}_{\frac{N}{g}+K-1}$$

$$若（a,m）=1则a^{\phi(m)} \equiv1(m)$$

$$2^{m-1} \equiv1(mod\ m)$$

#include <bits/stdc++.h>

const long long MAXN = 1000000,MOD = 1000000007;

using namespace std;
long long T,ans,N,K,cnt;
int mu[MAXN+5],prime[MAXN+5];
long long fnv[2*MAXN+5],fac[2*MAXN+5],inv[MAXN+5],f[MAXN+5],fib[MAXN+5];
bool vis[MAXN+5];

vector<long long>d;

inline long long powmod(long long a,long long b){
long long res=1;
a%=MOD;
for(;b;b>>=1){
if(b&1)res=res*a%MOD;
a=a*a%MOD;
}
return res;
}

inline void pre(){
fib[0] = 0;fib[1] = 1;inv[1] = 1;
fac[0] = fnv[0] = 1;
for(int i = 2;i <= MAXN;i++) fib[i] = (fib[i-1] + fib[i-2]) % (MOD - 1);
for(int i = 2;i <= MAXN;i++) inv[i] = (MOD-MOD/i)*inv[MOD%i]%MOD;
for(int i = 1;i<=2*MAXN;i++) {
fac[i] = fac[i-1] * i % MOD;
fnv[i] = fnv[i-1] * inv[i] % MOD;
}
mu[1] = 1;cnt = 0;
for(int i = 2;i <= MAXN;i++){
if(!vis[i]){
prime[cnt++] = i;
mu[i] = -1;
}
for(int j = 0;j < cnt&&i*prime[j] <= MAXN;j++){
vis[i*prime[j]] = true;
if(i%prime[j]) mu[i*prime[j]] = -mu[i];
else {
mu[i*prime[j]] = 0;
break;
}
}
}
}

inline long long comb(long long a,long long b){
return ((fac[a]*fnv[b])%MOD*fnv[a-b])%MOD;
}

int main()
{
pre();
scanf("%lld",&T);
while(T--){
scanf("%lld%lld",&N,&K);
d.clear();memset(f,0,sizeof(f));
for(int i = 1;i <= N;i++) if(N%i == 0) d.push_back(i);

for(int i = 0;i < d.size();i++)
for(int j = i;j < d.size();j++)
if(d[j]%d[i] == 0){
f[i] = ((f[i] + mu[d[j]/d[i]]*comb(N/d[j]+K-1,N/d[j]))%MOD + MOD)%MOD;
}

ans = 0;

for(int i = 0;i < d.size();i++) ans=(ans+f[i]*(powmod(2,fib[d[i]])-1))%MOD;

ans = ans * powmod(comb(N+K-1,K-1),MOD-2) % MOD;
if(ans < 0) ans += MOD;
printf("%lld\n",ans);
}
return 0;
}
Last modification：November 29th, 2018 at 10:45 am
If you think my article is useful to you, please feel free to appreciate