这道超大范围的题目能不能用python求解？

• Z时代
• 2024-02-23
• 分类：IT

题目描述

题目来源及自己的思路

题目来源
我的代码如下：

l,r,k = map(int,input().split())
def xiangxiaquzheng(a,k):
    return int((a**(1/k)))
sum = 0
for x in range(l,r+1):
    if x % xiangxiaquzheng(x,k) == 0:
        sum +=1
print(sum)

过不了！

相关代码

通过的c++

#include <bits/stdc++.h>
using i64 = long long;
using i128 = __int128;
std::istream &operator>>(std::istream &is, i128 &n) {
    n = 0;
    std::string s;
    is >> s;
    for (auto c : s) {
        n = 10 * n + c - '0';
    }
    return is;
}
std::ostream &operator<<(std::ostream &os, i128 n) {
    if (n == 0) {
        return os << 0;
    }
    std::string s;
    while (n > 0) {
        s += '0' + n % 10;
        n /= 10;
    }
    std::reverse(s.begin(), s.end());
    return os << s;
}
std::vector<i128> c, cs;
i128 largePower(i128 a, int b) {
    i128 ans = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            ans *= a;
        }
    }
    return ans;
}
int sqrtk(i128 x, int k) {
    i128 l = 0, r = 1E7;
    while (l <= r) {
        i128 m = (l + r) / 2;
        if (largePower(m, k) > x) {
            r = m - 1;
        } else {
            l = m + 1;
        }
    }
    return int(r);
}
i128 calc(i64 x, int k) {
    if (x == 0) {
        return 0;
    }
    int y = sqrtk(i128(x), k);
    i128 ans = cs[y - 1];
    x -= largePower(y, k) - 1;
    ans += (x + y - 1) / y;
    return ans;
}
std::vector comb(20, std::vector<i128>(20));
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    i64 l, r;
    int k;
    std::cin >> l >> r >> k;
    comb[0][0] = 1;
    for (int i = 1; i < 20; i++) {
        comb[i][0] = 1;
        for (int j = 1; j < 20; j++) {
            comb[i][j] = comb[i - 1][j] + comb[i - 1][j - 1];
        }
    }
    const int N = sqrtk(r, k) + 2;
    c.assign(N, 1);
    for (int i = 1; i < N; i++) {
        for (int j = 1; j < k; j++) {
            c[i] += comb[k][j] * largePower(i, k - j - 1);
        }
    }
    cs.resize(N + 1);
    for (int i = 0; i < N; i++) {
        cs[i + 1] = cs[i] + c[i + 1];
    }
    if (k == 1) {
        std::cout << r - l + 1 << "\n";
        return 0;
    }
    std::cout << calc(r, k) - calc(l - 1, k) << "\n";
    return 0;
}

你期待的结果是什么？实际看到的错误信息又是什么？

这代题目能不能用python解？
范围确实很大，但是就没办法么？

回答：

浮点运算时有误差的，int((a**(1/k))) 的结果并不准确，比如：

>>> print("{:.20f}".format(125**(1/3)))
4.99999999999999911182

你看 C++ 里都是用整数乘方之后比大小的，而不是直接开方下取整。

以上是 这道超大范围的题目能不能用python求解？ 的全部内容， 来源链接： utcz.com/p/938996.html