Sum of gcd of Tuples (Hard)

NC229748. Sum of gcd of Tuples (Hard)

描述

给 $\ n,k$ ，求：

$\sum_{a_1=1}^k \sum_{a_2=1}^k...\sum_{a_n=1}^k {gcd(a_1,a_2...a_n)}\ mod\ 10^9+7$

输入描述

第一行包含两个整数。

输出描述

输出一行表示答案。

示例1

输入:

3 2

输出:

说明:

gcd(1,1,1)+gcd(1,1,2)+gcd(1,2,1)+gcd(1,2,2)+gcd(2,1,1)+gcd(2,1,2)+gcd(2,2,1)+gcd(2,2,2)

=1+1+1+1+1+1+1+2

示例2

输入:

3 200

输出:

10813692

示例3

输入:

100000 100000

输出:

742202979

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++ 解法, 执行用时: 21ms, 内存消耗: 1164K, 提交时间: 2021-11-27 20:41:41

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
ll power(ll a,ll b){return b?power(a*a%mod,b/2)*(b%2?a:1)%mod:1;}

int main(){
    ll n,k;
    cin>>n>>k;
    ll dp[k+1],ans=0;
    for(ll i=k;i>=1;i--){
        dp[i]=power(k/i,n);
        for(ll j=2*i;j<=k;j+=i) dp[i]-=dp[j];
        ans=(ans+i*dp[i]%mod)%mod;
    }
    cout<<(ans+mod)%mod;
    return 0;
}

上一题

下一题

详情