### 样例

#### 输入

1
6 8

#### 输出

797202805

### 思路

$2^{f_{gcd(cnt_1,cnt_2,…,cnt_k}}-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<
 
 Share 【BZOJ 2820】YY 的 GCD / 题解 BZOJ原题地址 [https://www.lydsy.com/JudgeOnline/problem.php?id=2820] 洛谷原题地址 [https:… 09 Aug 2018 【百度之星 2018 资格赛】整数规划 / 题解 原题地址 [http://bestcoder.hdu.edu.cn/contests/contest_showproblem.php?cid=820&… 07 Aug 2018 
 
 
 Zepto's © 2024 Data & privacy Contact → Published with Ghost • Theme Attila • System theme 
 $(document).ready(function () { var viewport =$(window); var post = $('.post-content'); // Responsive videos with fitVids post.fitVids(); // Format code blocks and add line numbers function codestyling() {$('pre code').each(function(i, e) { // Code highlight hljs.highlightElement(e); // No lines for plain text blocks if (!$(this).hasClass('language-text')) { var code =$(this); // Calculate amount of lines var lines = code.html().split(/\n(?!$)/g).length; var numbers = []; if (lines > 1) { lines++; } for (i = 1; i < lines; i++) { numbers += '<span class="line" aria-hidden="true">' + i + '</span>'; } code.parent().append('<div class="lines">' + numbers + '</div>'); } }); } codestyling(); // Reading progress bar on window top function readingProgress() { var postBottom = post.offset().top + post.height(); var viewportHeight = viewport.height(); var progress = 100 - (((postBottom - (viewport.scrollTop() + viewportHeight) + viewportHeight / 3) / (postBottom - viewportHeight + viewportHeight / 3)) * 100);$('.progress-bar').css('width', progress + '%'); (progress > 100) ? $('.progress-container').addClass('complete'):$('.progress-container').removeClass('complete'); } readingProgress(); // Trigger reading progress viewport.on({ 'scroll': function() { readingProgress(); }, 'resize': function() { readingProgress(); }, 'orientationchange': function() { readingProgress(); } }); });