k=1的时候明显答案是(l+r)(r−l+1)2\dfrac{(l+r)(r-l+1)}{2}
k>=3的时候可以枚举值域，算出对应的长度然后把贡献加起来
k=2的时候推式子，考虑计算[1,l−1],[1,r][1,l-1],[1,r]的答案，那么相当于只需要推[1,n][1,n]的式子。
设x=⌊n⌋x=\lfloor n\rfloor，对于[x2,n][x^2,n]部分的答案容易算出是x(n−x2+1)x(n-x^2+1)；
对于[1,x2−1][1,x^2-1]的部分我们列出式子

∑i=1x−1i((i+1)2−i2)=∑i=1x−1i(2i+1)=x(x−1)(2x−1)3+x(x−1)2\sum\limits_{i=1}^{x - 1}i((i+1)^2-i^2)=\sum\limits_{i=1}^{x -1}i(2i+1)=\dfrac{x(x-1)(2x-1)}{3}+\dfrac{x(x-1)}{2}

然后就做完了。

ll ksm(ll a, ll b) {
    ll ans = 1;
    for (; b; b >>= 1, a *= a)
        if (b & 1)ans *= a;
    return ans;
}
ll calc(ll n) {
    ll x = sqrt((long long)n);
    return x * (x - 1) * (2 * x - 1) / 3 + x * (x - 1) / 2 + x * (n - x * x + 1);
}

int main() {
    ll l = fast_IO::read(), r = fast_IO::read(), k = fast_IO::read();
    if (k == 1)fast_IO::write((l + r) * (r - l + 1) / 2);
    else if (k == 2)fast_IO::write(calc(r) - calc(l - 1));
    else {
        ll ans = 0;
        for (ll i = 1; ksm(i - 1, k) <= r; ++i) {
            ll L = ksm(i - 1, k), R = ksm(i, k) - 1;
            L = max(L, l);
            R = min(R, r);
            if (L <= R)ans += (R - L + 1) * (i - 1);
        }
        fast_IO::write(ans);
    }
    return 0;
}