C++ 解法, 执行用时: 128ms, 内存消耗: 1240K, 提交时间: 2021-06-12 02:27:30

#include <bits/stdc++.h>
#define clog(x) std::clog << (#x) << " is " << (x) << '\n';
using LL = long long;

const int M = 1e9 + 9;
int pow(int x, int n) {
	int r = 1;
	while (n) {
		if (n & 1) r = 1LL * r * x % M;
		n >>= 1;   x = 1LL * x * x % M;
	}
	return r;
}
int Fib(int n) {
	int a = 0, b = 1, c = 1, d = 0;
	while (n) {
		if (n & 1) {
			int x = 1LL * a * c % M;
			a = (1LL * a * d + 1LL * b * c + x) % M;
			b = (1LL * b * d + x) % M;
		}
		n >>= 1;
		int x = 1LL * c * c % M;
		c = (2LL * c * d + x) % M;
		d = (1LL * d * d + x) % M;
	}
	return a;
}
// 没必要预处理的样子，懒得试了
std::unordered_map<int, int> mp;
int getans(int n) {
	if (mp.count(n)) return mp[n];
	int ans = Fib(n + 2) - 1;
	for (int i = 2, j; i <= n; i = j + 1) {
		j = n / (n / i);
		ans = (ans - 1LL * (j - i + 1) * getans(n / i)) % M;
	}
	if (ans < 0) ans += M;
	return mp[n] = ans;
}

int main() {
	// freopen("in", "r", stdin);
	std::cin.tie(nullptr)->sync_with_stdio(false);
	int n, k;
	std::cin >> n >> k;
	int ans = 0;
	for (int i = 1, j; i <= n; i = j + 1) {
		j = n / (n / i);
		ans = (ans + 1LL * (getans(j) - getans(i - 1)) * pow(n / i, k)) % M;
	}
	if (ans < 0) ans += M;
	std::cout << ans << '\n';
	return 0;
}