首页 > 其他分享 >DZY Loves Math

DZY Loves Math

时间:2023-06-24 19:56:30浏览次数:32  
标签:lfloor right frac sum times Loves DZY Math left

题面

对于正整数 \(n\),定义 \(f(n)\) 为 \(n\) 所含质因子的最大幂指数。例如 \(f(1960)=f(23×51×72)=3,f(10007)=1,f(1)=0\)。给定正整数 \(a,b\),求下式的值:

\[\sum_{i = 1}^a\sum_{j = 1}^bf(\gcd(a,b)) \]

题解

在下文的推导中,为避免歧义,设 \(N = \min(a,b), M = \max(a,b)\),显然 \(N \le M\)。

\[\displaystyle \begin{aligned} & \sum_{i = 1}^N \sum_{j = 1}^M f(\gcd(a,b))\\ = & \sum_{d = 1}^N f(d) \sum_{i = 1}^N \sum_{j = 1}^M \left[\gcd(i,j) = d\right] \\ = & \sum_{d = 1}^N f(d) \sum_{i = 1}^{\left\lfloor\frac{N}{d}\right\rfloor}\sum_{j = 1}^{\left\lfloor\frac{M}{d}\right\rfloor} \left[\gcd(i,j) = 1\right] \\ = & \sum_{d = 1}^N f(d) \sum_{i = 1}^{\left\lfloor\frac{N}{d}\right\rfloor}\sum_{j = 1}^{\left\lfloor\frac{M}{d}\right\rfloor} \varepsilon(\gcd(i,j)) \\ = & \sum_{d = 1}^N f(d) \sum_{i = 1}^{\left\lfloor\frac{N}{d}\right\rfloor}\sum_{j = 1}^{\left\lfloor\frac{M}{d}\right\rfloor} \sum _{t \mid \gcd(i, j)} \mu(t)\\ = & \sum_{d = 1}^N f(d) \sum_{i = 1}^{\left\lfloor\frac{N}{d}\right\rfloor}\sum_{j = 1}^{\left\lfloor\frac{M}{d}\right\rfloor} \sum _{t \mid i \land t \mid j} \mu(t)\\ \end{aligned}\]

设 \(T = dt\),那么:

\[\displaystyle \begin{aligned} & \sum_{d = 1}^N f(d) \sum_{i = 1}^{\left\lfloor\frac{N}{d}\right\rfloor}\sum_{j = 1}^{\left\lfloor\frac{M}{d}\right\rfloor} \sum _{t \mid i \land t \mid j} \mu(t)\\ = & \sum_{T = 1}^N {\left\lfloor\frac{N}{T}\right\rfloor} {\left\lfloor\frac{M}{T}\right\rfloor} \sum_{d \mid T} f(d) \mu(\frac{T}{d}) \end{aligned}\]

设 \(h = f * \mu\),那么原式可化为:

\[\displaystyle \sum_{T = 1}^N {\left\lfloor\frac{N}{T}\right\rfloor} {\left\lfloor\frac{M}{T}\right\rfloor} h(T) \]


下面考虑求函数 \(h(n)\) 的值,首先对 \(n\) 进行质因数分解:

\[\displaystyle n = \prod_{i = 1}^m p_i^{c_i} \ ( \ p_i \in \mathbb{P}, c_i \ge 1 \ )\]

发现可以把 \(h(n)\) 写成如下形式:

\[\displaystyle h(n) = \sum_{ab = n} f(a) \mu(b) \]

考虑到莫比乌斯函数 \(\mu(n)\) 的性质:如果 \(n\) 中含有平方质因子那么 \(\mu(n) = 0\)。
所以可以得出能产生贡献的 \(b\) 即满足 \(\mu(b) \ne 0\) 的 \(b\) 一定满足:

\[\displaystyle b = \prod_{i = 1}^m p_i^{d_i} \ ( \ p_i \in \mathbb{P}, _i \in \{0, 1\} \ )\]

所以可以得出 \(f(a) = l \lor f(a) - l - 1\)。

设 $l = \max \limits_{i = 1}^m c_i,k = \sum \limits_{i = 1}^m \left[ c_i = l\right] $。接下来按 \(k \ne m\) 和 \(k = m\) 两种情况分类讨论 \(h(n) 的值\)。

当 \(k \ne m\) 时,按 \(f(a) = l\) 和 \(f(a) = l - 1\) 两种子情况讨论。

当 \(f(a) = l\) 时,设在 \(k\) 个满足 \(c_i = l\) 的质数中选了 \(t\) 个,在另外 \(m - k\) 个质数中选了 \(s\) 个,那么可以得出贡献为:

\[\displaystyle \begin{aligned} & \sum_{s = 0} ^ {m - k} \sum_{t = 0}^{k - 1} \dbinom{k}{t} \times l \times (-1) ^ {s + t} \times \dbinom{m - k}{s}\\ = & \sum_{t = 0}^{k - 1} \dbinom{k}{t} \times l \times (-1) ^ {t} \sum_{s = 0} ^ {m - k} (-1) ^ {s} \times 1^{m - k - s} \dbinom{m - k}{s} \\ = & 0 \end{aligned}\]

当 \(f(a) = l - 1\) 时,\(k\) 个满足 \(c_i = l\) 的质数中一定全部选上,设在另外 \(m - k\) 个质数中选了 \(s\) 个,那么可以得出贡献为:

\[\displaystyle \begin{aligned} & \sum_{s = 0} ^ {m - k} (l - 1) \times (-1) ^ {s} \times \dbinom{m - k}{s}\\ = & \sum_{s = 0} ^ {m - k} (l - 1) \times (-1) ^ {s}\times 1^{m - k - s} \dbinom{m - k}{s} \\ = & (l - 1) \times \sum_{s = 0} ^ {m - k} (-1) ^ {s}\times 1^{m - k - s} \dbinom{m - k}{s}\\ = & 0 \end{aligned}\]

当 \(k = m\) 时,有 \(f(a) = l\) 和 \(f(a) = l - 1\) 两种子情况,可以得出贡献为:

\[\displaystyle \begin{aligned} & \sum_{s = 0} ^ {m - 1} (l) \times (-1) ^ {s} \times \dbinom{m - k}{s} + (l - 1) \times (-1) ^ {m} \times \dbinom{m - k}{m - k}\\ = & \sum_{s = 0} ^ {m} (l) \times (-1) ^ {s} \times \dbinom{m - k}{s} - 1 \times (-1) ^ m\\ = & - 1 \times (-1) ^ m \\ = & (-1) ^ {m + 1} \end{aligned}\]

综上可以得出 \(h(n)\) 的计算式:

\[h(n)=\begin{cases} 0 & k \ne m\\ (-1)^{m + 1} & k = m \end{cases}\]


下面考虑如何高效的预处理出 \(h(n)\) 的值。

考虑一下欧拉筛在筛出合数 \(\displaystyle n = \prod_{i = 1}^m p_i^{c_i} \ ( \ p_i \in \mathbb{P}, c_i \ge 1 , p_i < p_{i + 1})\) 时的路径:

\[p_m \rightarrow p_m^2 \rightarrow p_m^3 \rightarrow \cdots \rightarrow p_m^{c_m} \rightarrow \\ p_{m - 1} p_m^{c_m} \rightarrow p_{m - 1}^2 p_m^{c_m} \rightarrow \cdots n\]

也就是说一个合数被筛出的路径是按质因子从大到小的顺序筛出的,所以可以开三个数组 \(preCount,nowCount\) 和 \(factorCount\),分别记录当前数的最小质因子的幂次,其他所有质因子的幂次和本质不同的质因子的个数。

如果在筛的过程中,设 \(i\) 为当前筛的数, \(j\) 为枚举的质数,\(t = i \cdot j\),如果 \(j \nmid i\),也就是说 \(j\) 不是 \(i\) 的质因子,但是其是 \(t\) 的最小质因子,所以 \(nowCount[t] = 1\),但是 \(preCount[t]\) 的值要根据 \(nowCount[i]\) 和 \(preCount[i]\) 的值来考虑:如果两者相等,直接赋值即可;否则直接赋 \(-1\),也就是说现在这个欧拉筛上的路径上的数的质因子幂次不可能相等了。如果 \(j \mid i\),直接累加即可。

Code

#include <bits/stdc++.h>

typedef long long valueType;
constexpr valueType maxN = 1e7 + 5;

class LineSieve {
public:
    typedef long long valueType;
    typedef std::vector<valueType> container;

private:
    valueType size;
    container minFactorList;
    container primeList;
    container preCount, nowCount, factorCount, data, sum;

public:
    explicit LineSieve(valueType _size_) : size(_size_), minFactorList(_size_ + 1), 
    preCount(_size_ + 1, 0),nowCount(_size_ + 1, 0), 
    factorCount(_size_ + 1), data(_size_ + 1),sum(_size_ + 1) {
        primeList.reserve((size_t) std::floor(std::log((long double) (_size_ + 1))));

        for (valueType i = 2; i <= size; ++i) {
            if (minFactorList[i] == 0) {
                primeList.push_back(i);
                minFactorList[i] = i;
                nowCount[i] = 1;
                preCount[i] = 0;
                factorCount[i] = 1;
                data[i] = 1;
            }

            for (auto const &iter: primeList) {
                valueType const t = i * iter;

                if (t > size)
                    break;

                minFactorList[t] = iter;

                if (i % iter == 0) {
                    nowCount[t] = nowCount[i] + 1;
                    preCount[t] = preCount[i];
                    factorCount[t] = factorCount[i];

                    break;
                } else {
                    nowCount[t] = 1;
                    preCount[t] = (nowCount[i] == preCount[i] || preCount[i] == 0) ? nowCount[i] : -1;
                    factorCount[t] = factorCount[i] + 1;
                }
            }
        }

        for (int i = 2; i <= size; ++i)
            if (nowCount[i] == preCount[i] || preCount[i] == 0)
                data[i] = (factorCount[i] & 1) == 1 ? 1 : -1;
            else
                data[i] = 0;

        std::partial_sum(data.begin(), data.end(), sum.begin());
    }

    valueType ans(valueType x) const {
        if (x > size)
            throw std::range_error("Larger than Size.");

        if (x < 0)
            throw std::range_error("Too small.");

        return sum[x];
    }
};

int main() {
    valueType T;

    std::cin >> T;

    LineSieve Euler(maxN);

    typedef std::function<valueType(valueType, valueType)> solveFunction;

    solveFunction solve = [&Euler](valueType N, valueType M) -> valueType {
        if (N > M)
            std::swap(N, M);

        valueType result = 0;

        valueType l = 1, r;

        while (l <= N) {
            r = std::min(N / (N / l), M / (M / l));

            result += (Euler.ans(r) - Euler.ans(l - 1)) * (N / l) * (M / l);

            l = r + 1;
        }

        return result;
    };

    for (int i = 1; i <= T; ++i) {
        valueType N, M;

        std::cin >> N >> M;

        std::cout << solve(N, M) << '\n';
    }

    std::cout << std::flush;

    return 0;
}

标签:lfloor,right,frac,sum,times,Loves,DZY,Math,left
From: https://www.cnblogs.com/User-Unauthorized/p/dzy-loves-math.html

相关文章

  • 2023 math
    已知集合\(M=\left\{-2,-1,0,1,2\right\}\),\(N=\left\{x\left|x^{2}-x-6\geq0\right.\right\},\)则\(M\capN=\)A.\(\{-2,-1,0,1\}\)B.\(\{0,1,2\}\)C.\(\{-2\}\)D.22.已知\(z=\frac{1-i}{2+2i}\),则\(z-\overline{z}=\)A.-iB.i......
  • [Ynoi2019 模拟赛] Yuno loves sqrt technology I
    题目Link分块,首先预处理所有整块之间的答案,这部分用类似莫队二离的手法可以改成\(O(n)\)次插入和\(O(n\sqrt{n})\)查询,然后根号平衡一手做到\(O(n\sqrt{n})\);空间自然也是能线性的。当然更直白的说法是,直接预处理\(f(i,j)\)表示前\(i\)块中\(>j\)的元素个数。然后考......
  • (十)Math对象API、数学对象、布尔对象
    一、MathAPI 二、数字对象 三、布尔对象 ......
  • MATH is the LOGIC OF CERTAINTY and STATISTICS is the LOGIC OF UNCERTAINTIES
    Statistics110ofHarvardUniversity: Mathisthelogicofcertainty,Statisticsisthelogicofuncertainty. Strategicpractice:Clarity;Honesty......
  • 【MathJax】语法总结
    基础语法1.显示公式在行中显示的(inlinemode),就用$...$单独一行显示(displaymode),则用$$...$$2.希腊字母要显示希腊字母,可以用\alpha,\beta,…,\omega,输出\(\alpha,\beta,…,\omega\)想要显示大写的话,就用\Gamma,\Delta,…,\Omega,输出\(\Gamma,\Delta,......
  • 电源参数计算常用的Mathcad功能介绍
    mathcad作为一款常用的数学计算软件,在很多个领域都用应用。本文用于总结在电源参数计算常用的功能或者函数。  一、分段函数在变量后面输入英文状态下的]键,就能出现分段函数的格式,将函数f(x)分为两段,再次按]键,将函数分为三段。不过分段函数一般是结合其他函数命令......
  • js Math
    JavaScript中的Math对象是一个数学库,提供了许多数学函数和常量,可以用于进行各种数学计算和运算。以下是Math对象的一些常用属性和方法:常量:Math.PI:圆周率。Math.E:自然对数的底数。数学函数:Math.abs(x):返回x的绝对值。Math.ceil(x):返回大于或等于x的最小整数。Math.fl......
  • Codeforces Round #287 (Div. 2)-D. The Maths Lecture(数位dp)
    原题链接D.TheMathsLecturetimelimitpertestmemorylimitpertestinputoutputAmrdoesn'tlikeMathsashefindsitreallyboring,soheusuallysleepsinMathsl......
  • Math类及静态导入
    知识点:Math含义:数学类,提供了一下数学运算的功能他是一个final类(说明他没有子类)并且所有的属性和方法都是静态的(标准的工具类)publicstaticvoidmain(String[]args){ System.out.println("求a的b次方:"+Math.pow(3,3));//27.0 System.out.println("求平方根:"+Math......
  • 用Mathematica和SciPy阐明Jacobi椭圆函数的定义方法
    这,这个,那,那个Jacobi椭圆函数SN和CN类似于三角函数正弦和余弦。它们出现在非线性振动和保形映射等应用中。不幸的是,定义这些函数有多种约定。这篇文章的目的是澄清围绕这些不同公约的混淆。上面的图像是函数sn[1]的一个图。模量、参数和模数角Jacobi函数有两个输入。我们通常认为Jac......