数论题中(杜教筛)交换求和符号

数论题中(杜教筛)交换求和符号文章目录方阵下三角约数倍数狄利克雷卷积以及杜教筛学习笔记突然对交换求和符号有了新的理解了,用矩阵转置的思路就很好理解,外层循环相当于枚举行,内层枚举列,交换次序就是先枚举列,再枚举行方阵正常的就是∑i=1n∑j=1nf(i,j)=∑j=1n∑i=1nf(i,j)\sum_{i=1}^n\sum_{j=1}^nf(i,j)=\sum_{j=1}^n\sum_{i=1}^nf(i,j)…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用


狄利克雷卷积 以及 杜教筛学习笔记

突然对交换求和符号有了新的理解了,用矩阵转置的思路就很好理解,外层循环相当于枚举行,内层枚举列,交换次序就是先枚举列,再枚举行

方阵

正常的就是 ∑ i = 1 n ∑ j = 1 n f ( i , j ) = ∑ j = 1 n ∑ i = 1 n f ( i , j ) \sum_{i=1}^n \sum_{j=1}^nf(i,j)=\sum_{j=1}^n \sum_{i=1}^nf(i,j) i=1nj=1nf(i,j)=j=1ni=1nf(i,j)

再写成习惯的i在外面,j在里面,相当于换哈元 = ∑ i = 1 n ∑ j = 1 n f ( j , i ) =\sum_{i=1}^n \sum_{j=1}^nf(j,i) =i=1nj=1nf(j,i)
相当于原来元素 f ( i , j ) f(i,j) f(i,j)的位置变成了 f ( j , i ) f(j,i) f(j,i)

下三角

∑ i = 1 n ∑ j = i n f ( i , j ) = ∑ j = 1 n ∑ j = i n f ( i , j ) \sum_{i=1}^n \sum_{j=i}^nf(i,j)=\sum_{j=1}^n \sum_{j=i}^nf(i,j) i=1nj=inf(i,j)=j=1nj=inf(i,j)
这个就是常见的去重的时候的枚举,行数不超过列数
同样想成想成先枚举列再枚举行
换哈元 = ∑ i = 1 n ∑ j = i n f ( j , i ) =\sum_{i=1}^n \sum_{j=i}^nf(j,i) =i=1nj=inf(j,i)和上面差不多

约数倍数

如果上面的很容易理解来试一哈这种约数倍数的哇,这个就是像杜教筛的题里面要用到的
∑ i = 1 n ∑ j ∣ i n f ( i , j ) = ? \sum_{i=1}^n\sum_{j|i}^nf(i,j)=? i=1njinf(i,j)=?
其中 i ∣ j i|j ij是表示 i 是 j i是j ij的约数,比如当 j = 6 j=6 j=6的时候, i i i就要枚举 1 , 2 , 3 , 6 1,2,3,6 1,2,3,6

这个也要从矩阵转置的角度来看,长得也和下三角差不多,只不过没有完全填充

交换次序就是先枚举列再枚举行,变成
∑ j = 1 n ∑ j ∣ i n f ( i , j ) \sum_{j=1}^n\sum_{j|i}^nf(i,j) j=1njinf(i,j)
这里内层求和还是 j 是 i 的 约 数 , i 是 j 的 倍 数 , 也 就 是 i = k j , k = 1 , 2 , 3… j是i的约数,i是j的倍数,也就是i=kj,k=1,2,3… ji,ij,i=kj,k=1,2,3...
所以在内层求和我们就阔以直接除以 j j j,这样 i i i就阔以从 1 1 1开始枚举了
变成 ∑ j = 1 n ∑ i = 1 [ n j ] f ( i j , j ) , 因 为 要 保 持 不 变 , 里 面 就 要 变 成 f ( i ⋅ j , j ) \sum_{j=1}^n\sum_{i=1}^{[\frac{n}{j}]}f(ij,j),因为要保持不变,里面就要变成f(i\cdot j,j) j=1ni=1[jn]f(ij,j),,f(ij,j)
然后再换一哈字母变成熟悉的样子,就变成了:
∑ i = 1 n ∑ j = 1 [ n i ] f ( j i , i ) \sum_{i=1}^n\sum_{j=1}^{[\frac{n}{i}]}f(ji,i) i=1nj=1[in]f(ji,i)
最 终 的 等 式 就 是 : ∑ i = 1 n ∑ j ∣ i n f ( i , j ) = ∑ i = 1 n ∑ j = 1 [ n i ] f ( j i , i ) 最终的等式就是:\sum_{i=1}^n\sum_{j|i}^nf(i,j)=\sum_{i=1}^n\sum_{j=1}^{[\frac{n}{i}]}f(ji,i) :i=1njinf(i,j)=i=1nj=1[in]f(ji,i)
那我们就用杜教筛的式子来套一哈喃,看对不对,原等式是这样的:
∑ i = 1 n ∑ d ∣ i n g ( d ) ⋅ f ( i d ) = ∑ i = 1 n g ( i ) ⋅ ∑ j = 1 n i f ( j ) \sum_{i=1}^n\sum_{d|i}^ng(d)\cdot f(\frac{i}{d})=\sum_{i=1}^ng(i)\cdot \sum_{j=1}^{\frac{n}{i}}f(j) i=1nding(d)f(di)=i=1ng(i)j=1inf(j)
这里把 j j j换成 d d d更有约数这个含义一些,不影响,其中的
∑ i = 1 n ∑ d ∣ i n g ( d ) ⋅ f ( i d ) = ∑ i = 1 n ∑ d = 1 [ n i ] g ( d ) ⋅ f ( d i d ) = ∑ i = 1 n ∑ d = 1 [ n i ] g ( d ) ⋅ f ( i ) , 然 后 g ( d ) 阔 以 提 出 去 = ∑ i = 1 n g ( i ) ⋅ ∑ j = 1 n i f ( j ) \sum_{i=1}^n\sum_{d|i}^ng(d)\cdot f(\frac{i}{d})=\sum_{i=1}^n\sum_{d=1}^{[\frac{n}{i}]}g(d)\cdot f(\frac{di}{d})=\sum_{i=1}^n\sum_{d=1}^{[\frac{n}{i}]}g(d)\cdot f(i),然后g(d)阔以提出去=\sum_{i=1}^ng(i)\cdot \sum_{j=1}^{\frac{n}{i}}f(j) i=1nding(d)f(di)=i=1nd=1[in]g(d)f(ddi)=i=1nd=1[in]g(d)f(i),g(d)=i=1ng(i)j=1inf(j)
嗯(✪ω✪)一模一样٩(๑>◡<๑)۶

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/182682.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • OCP-1Z0-051-标题决心-文章2称号

    OCP-1Z0-051-标题决心-文章2称号

  • 数组和链表的区别?「建议收藏」

    数组和链表的区别?「建议收藏」今天来说下两种最基本的数据结构——数组和链表,它们无处不在!下面我们来一一介绍下他们,首先了解下内存分配的!内存的工作原理假设你去看演出,需要将东西寄存。寄存处有一个柜子,柜子有很多抽屉。每个抽屉可放一样东西,你有两样东西要寄存,因此要了两个抽屉。现在你可以去看演出了!这大致就是计算机内存的工作原理。计算机就像是很多抽屉的集合体,每个抽屉都有地址。fe0ffeeb是一个内存单元的地址。需要将数据存储到内存时,你请求计算机提供存储空间,计算机给你一个存储地址。需要存储多项数据时,有两种基本方式

  • 一篇教会你写90%的shell脚本_flash动画脚本怎么写

    一篇教会你写90%的shell脚本_flash动画脚本怎么写如果将运维比作手链,将珍珠比作服务,那么将珍珠串起来的线就是Shell,作为实现Linux系统自动管理以及自动化运维所必备的Shell脚本,其重要性便不言而喻。每一位合格的Linux系统管理员或运维工程师,都应该将熟练编写Shell脚本视为基本技能之一,只有这样才能减少不必要的劳动。但是新人在编写脚本时却只会:#!/bin/bash,所以今天就给大家分享100个经典实用的脚本范例,手把手教你写Shell脚本。这100个脚本范例从基础到进阶均涵盖,有侧重地提高编写能力,结构清晰准确,PDF格式,可

  • ant man什么意思_汽车的ANT是什么意思?

    展开全部ANT就是天线接口,用来连接天线。常见于收音机,或者GPS等上面。在接收短波或FM时需62616964757a686964616fe58685e5aeb931333433626437要外界天线,以增加接收灵敏度。作为高速数据传输领域的新成员,它在智能网联汽车中所起到的作用是举足轻重的。传统汽车对于天线的需求非常有限,仅仅在于接收一些较低频率的AM/FM信号、GPS信号,以及近两年才开始普及…

  • Offsetof用法「建议收藏」

    Offsetof用法「建议收藏」#include<stddef.h>#include<stdio.h>structaddress{charname[50];charstreet[50];intphone;};intmain(){printf(“address结构中的name偏移=%d字节。\n”,offsetof(structaddress,name));printf(“address结构中的street偏移=%d字节。\n”,offsetof(s

  • MyBatis架构与源码分析<资料收集>

    MyBatis架构与源码分析<资料收集>

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号