考完试再来写心得吧…

//#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define sync ios::sync_with_stdio(false)
#define MOD 1000000007
#define debug freopen("D:\\Learn C++\\w.txt", "w", stdout)
#define maxN 10000004

using namespace std;

typedef unsigned long long ull;

vector<ull> Prime;
bool isPrime[maxN] = {};
ull p[maxN] = {}, pe[maxN] = {}, g[maxN] = {}, k;

void Euler(ull n){
    for(ull i = 2; i <= n; i++){
        if(isPrime[i]) {
            Prime.push_back(i);
            p[i] = pe[i] = i;
        }
        for(int j = 0; j < Prime.size() && i * Prime[j] <= n; j++) {
            ull op = i * Prime[j];
            isPrime[op] = false;
            if(Prime[j] == p[i]){
                p[op] = p[i], pe[op] = pe[i] * p[i] % MOD;
            }
            else{
                if(p[i] < Prime[j]){
                    p[op] = p[i], pe[op] = pe[i];
                }
                else{
                    p[op] = Prime[j], pe[op] = Prime[j];
                }
            }
            if(!(i % Prime[j]))
                break;
        }
    }
}

ull fastPower(ull base, ull power){
    ull ans = 1;
    while(power){
        if(power & 1)
            ans = base * ans % MOD;
        power >>= 1, base = base * base % MOD;
    }
    return ans;
}

ull calc(ull num){
    if(num == 1)
        return 1;
    if(g[num])
        return g[num];
    return (g[num] = (calc(pe[num]) * calc(num / pe[num])) % MOD);
}

void init(ull n){
    for(int i = 0; i < Prime.size(); i++){
        ull power = 1, inv = fastPower(Prime[i] - 1, MOD - 2);
        for(ull j = Prime[i]; j <= n; j *= Prime[i], power++){
//            if(Prime[i] == 2) {
//                g[j] = fastPower(2, power * k + 1) - 1;
//                continue;
//            }
            g[j] = ((fastPower(Prime[i], power * k + 1) - 1) % MOD * inv % MOD) % MOD;
        }
    }
}

int main() {
    ull ans = 1, n;
    cin >> n >> k;
    memset(isPrime, true, sizeof(isPrime));
    Euler(n);
    init(n);
    for (ull i = 2; i <= n; i++) {
        ans = (ans + calc(i)) % MOD;
    }
    cout << ans << endl;
}

终于tmd过了啊!