c++ 因子与模算子和 _大数据知识库

这个问题由一个函数S（i）组成，它将某个数的所有可能的除数求和，所以S（18）=1+2+3+6+9+18=39。在此情况下，我们必须计算值为1到n的S（i）%MOD的和。其中η最高为10 ^12。
这里我使用了每个i的约数的出现（通过使用公式出现= q = floor（n/i））。以及公式floor（n/q）来查看与另一个数字共享该出现的最后一个数字i。最后，我使用算术和公式对所有具有相同出现次数的除数求和，并将它们乘以q，将i值移动跳过的值的数量，因为我们已经知道它们的出现次数。我的问题是，接近非常大的数字代码失败，提供了一个错误的答案并失败了测试。

#include <iostream>
#include <cmath>
using namespace std;
const int MOD = 1000000007;
int main() {
    long long n;
    cin >> n;
    long long ans = 0;
    long long q = 0;
 
    long long a = 0;
    long long s = 0;
    long long ultimo_i = 0;
   for (long long i=1;i<=n;) {
        q = static_cast<long long>(floor(n / i));
        ultimo_i = static_cast<long long>(floor(n) / q);
        a = (ultimo_i - i + 1);
        s = ((i+ultimo_i) * a) / 2;
        ans += (s * q);
        i += a;
    }
    
    ans %= MOD;
    cout << ans << endl;
    return 0;
}

预期的结果不能表示为long long，它太大了，实际上OP的代码应该输出结果 * 模 * 1，000，000，007。
然而，为了获得正确的值，我们应该在计算的每个合理步骤使用模算术属性。
这基本上意味着你必须在每个值和中间结果（每次求和或乘法之后）应用% 1,000,000,007LL，这些结果将超出所用类型的范围。
请注意，为模选择的特定值，除了成为素数之外，也足够小，可以安全地平方为long long（但是太大不能被提升到3次幂），但（一般来说）不是int（像OP的代码），这在大多数系统中是32位宽的类型。
为了计算/ 2，我们需要找到2相对于所述模数的modular multiplicative inverse。换句话说，我们需要找到 x 使得

2 ∙ *x* ≡ 1  (mod 1,000,000,007)

我们可以不使用任何一种适当的形式化方法，而只观察到

(1,000,000,007 + 1) / 2 = 500'000'004   -->   2 ∙ 500'000'004 ≡ 1  (mod 1,000,000,007)

所以，要除以2，我们只需要 * 乘以 * 500'000'004，然后取模（% 1,000,000,007）。
在发布的代码中还有另一个问题：

long long n;
long long q;
// ...
for (long long i=1;i<=n;) {
    q = static_cast<long long>(floor(n / i));
    //  ^^^^^^^^^^^^^^^^^^^^^^ ^^^^^^
    
    // ...
}

没有必要使用std::floor，它返回一个double。该操作n / i已经是一个整数除法，产生类型为long long的n/i。将整数转换为浮点数再转换为整数只是浪费。

展开查看全部

c++ 因子与模算子和

1条答案

相关问题

热门标签

最新问答