C++(g++ 7.5.0) 解法, 执行用时: 939ms, 内存消耗: 452K, 提交时间: 2022-10-24 23:03:23

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int maxn = 2e5+8, inf = 1e18+9, mod = 1e9+7;

signed main() {
    cin.tie(0)->sync_with_stdio(false), cout << fixed << setprecision(15);
    int n, k; cin >> n >> k;
    auto qpow = [&](int a, int b) {
        int res = 1;
        while (b) {
            if (b & 1) res = (res * a) % mod;
            a = (a * a) % mod;
            b >>= 1;
        }
        return res;
    };
    int ans = 0;
    for (int i = 1; i <= n; i++) ans = (ans + n / i * qpow(i, k)) % mod;
    cout << ans << endl;
    return 0;
}

Java(javac 1.8) 解法, 执行用时: 1512ms, 内存消耗: 12368K, 提交时间: 2019-05-11 20:42:00

import java.math.BigInteger;
import java.util.Scanner;


public class Main {
	public static final long mod = 1000000007;
	public static long qpow(long a, long b) {
		long ans = 1;
		while (b != 0) {
			if ((b & 1) == 1) {
				ans = (ans * a) % mod;
			}
			a = (a * a) % mod;
			b >>= 1;
		}
		return ans;
	}
	public static void main(String [] ages){
		Scanner cin = new Scanner(System.in);
		int n, k;
		n = cin.nextInt(); k = cin.nextInt();
		long ans = 0;
		for (int d = 1; d <= n; d++) {
			ans += (n / d * qpow(d, k)) % mod;
			ans %= mod;
		}
		System.out.println(ans);
	}
}

C++14(g++5.4) 解法, 执行用时: 834ms, 内存消耗: 156920K, 提交时间: 2020-07-22 22:58:49

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e7+10,mod=1e9+7;
int pw[N],n,k,vis[N],res;
int qmi(int a,int b){
	int res=1;
	while(b){if(b&1) res=res*a%mod; a=a*a%mod; b>>=1;}
	return res;
}
void sieve(){
	pw[1]=1;
	for(int i=2;i<=n;i++){
		if(!vis[i]){
			pw[i]=qmi(i,k);
			for(int j=i+i;j<=n;j+=i)	vis[j]=i;
		}else	pw[i]=pw[vis[i]]*pw[i/vis[i]]%mod;
	}
} 
signed main(){
	cin>>n>>k;	sieve();
	for(int i=1;i<=n;i++)	res=(res+pw[i]*(n/i))%mod;
	cout<<res;
	return 0;
}

C++(clang++11) 解法, 执行用时: 910ms, 内存消耗: 396K, 提交时间: 2021-03-08 15:56:48

#include<bits/stdc++.h>
using namespace std;
#define int long long
int fact[200010];
int infact[200010];
const int mod=	1e9+7; ;
int qmi(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1)	res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res;
}
int c(int a,int b)
{
	return fact[a]*infact[b]%mod*infact[a-b]%mod;
}	
int n,k;
signed main()
{
	cin>>n>>k;
	int res=0;
	for(int i=1;i<=n;i++)
	{
		res=(res+(n/i)*qmi(i,k)%mod)%mod;
	}
	cout<<res<<endl;
}