bzoj 2956: 模积和-白红宇

bzoj 2956: 模积和

阅读量：259 次

发布时间：2019-03-01

本文共 1762 字，大约阅读时间需要 5 分钟。

为了解决这个问题，我们需要计算一个数学表达式，它涉及到求和和模运算。这个表达式可以分解为两个部分：首先是双重求和，然后是减去相等的情况。我们将使用C++编写代码来高效地计算结果。

问题分析

我们需要计算以下表达式：∑_{n}^i ∑_{m}^j (n mod i) * (m mod j)，其中i ≠ j。

为了高效计算，我们首先将问题分解为两个部分：

单独计算每个变量的总和。

处理两个变量的联合求和。

方法思路

单独求和：我们先计算每个变量的总和，分别使用solve(n)和solve(m)来处理。

联合求和：我们使用solve2(n, m)来处理两个变量的联合求和，同时考虑它们的大小关系。

模运算：由于结果可能很大，我们在每一步都使用模运算来保持结果在合理范围内。

解决代码

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;const LL mod = 19940417;const LL inv = 3323403;LL sum(LL l, LL r) {    return ((LL)(r - l + 1) * (LL)(l + r) / 2) % mod;}LL sum_2(LL n) {    return ((LL)n * (LL)(n + 1) % mod * (LL)(2 * n + 1) % mod * inv % mod;}LL solve(LL n) {    LL ans = 0;    LL pos;    for (LL i = 1; i <= n; i = pos + 1) {        pos = (n / (n / i));        LL term = (n * (pos - i + 1) - (n / i) * sum(i, pos)) % mod;        ans = (ans + term) % mod;    }    return ans;}LL solve2(LL n, LL m) {    if (n > m) swap(n, m);    LL ans = 0;    LL pos;    for (LL i = 1; i <= n; i = pos + 1) {        pos = min(n / (n / i), m / (m / i));        LL t1 = (n * m % mod) * (pos - i + 1) % mod;        LL t2 = ((n / i) % mod) * sum(i, pos) % mod;        LL t3 = ((m / i) % mod) * ((sum_2(pos) - sum_2(i - 1)) % mod) % mod;        LL t3 = (t3 + mod) % mod;        LL term = (t1 - t2 + t3) % mod;        ans = (ans + term) % mod;    }    return ans;}LL n, m;int main() {    scanf("%lld %lld", &n, &m);    LL res = (solve(n) * solve(m) % mod - solve2(n, m)) % mod;    res = (res + mod) % mod;    printf("%lld", res);}

代码解释

include 和宏定义：包含了必要的头文件和常量定义，模数为19940417，逆元为3323403。

sum 函数：计算从l到r的和，并对结果取模。

sum_2 函数：计算从1到n的平方和，并对结果取模。

solve 函数：计算单独变量的总和，使用递归求和的方法。

solve2 函数：计算两个变量的联合总和，考虑了它们的大小关系。

主函数：读取输入，计算结果并输出。

通过这个方法，我们可以高效地计算所需的数学表达式，并确保结果在合理范围内。

转载地址：http://rdza.baihongyu.com/

你可能感兴趣的文章