什么是邮件列表(Mailing List)?

这是一个对知乎问题的回答,什么是邮件列表(mailing list)?

简单的来说就是一组接收者的集合,他可以表示为一个邮箱地址,你向这个地址发送邮件,这个地址会帮你转发给其他用户。本质上就是一对多发信。

相对于抄送、秘抄需要将每个收信者写到邮件头中,这个列表是可以动态变化的,新的接收者可以通过网页或者其他方式告诉邮件列表自己愿意接收向这个邮件列表发送的邮件,同理也可以退出。

请区别各大邮件商提供的服务,如QQ的群邮件以及所谓订阅列表,邮件列表是平台无关的,邮件列表服务商不一定必须与发送者接收者同在一个服务商下,而且邮件列表应该使用的是通用的邮箱地址标识符(如me@example.com),不应该用QQ号什么的作为标识。

邮件列表可以用来做消息订阅,也可以用来做社区。具体例子就是你收到的各种推广信息从一种程度上可以认为是一种邮件列表。另外国外的较大型开源社区一般使用邮件列表作为其沟通的工具。

邮件列表相对于bbs等网上论坛,发信较为麻烦,实时性不高(分钟级,相比于IM即时通讯的秒级),学习成本比较高,又因为其去中心化的特点(每个人都可以作为邮件列表),较难审查(不是不行,邮件列表不是审查安全的信息交流工具),在国内一直没有推广开来(国内的公共邮件列表服务商少的可怜啊)。

其实邮件列表还是蛮有价值的,他不绑定任何一个平台,这意味着,你只要有一个有一定信誉的邮件服务商账户,你可以向世界上任何地方任何服务商的人们构建一个群组。不像微信,你不可以跟QQ用户组群。而且正因为邮件发送有一定门槛,人们一般会倾向于使用正式文体,讨论文体的效率会稍微高那么一丢丢。

OpenWrt 使用自带的 Dnsmasq 屏蔽网站(设置解析)

有些时候,我们可能希望屏蔽一个网站(例如:屏蔽小米广告),或者为特定的网站设置一个解析(例如:自己网站发布前在本地进行测试)。OpenWrt 提供了一个比本地 Host 强大许多的解析工具 Dnsmasq ,相比于本地 Host,他支持通配,并且可以解析特殊类型的记录。

网上有教程,需要安装 adblock 什么的,但其实就是一行(准确的来说是三行)命令的事情(luci 上没有提供修改的位置,所以不能在网页上解决)。

# 设置 example.com 域名 a 类型记录为 192.168.0.1
uci add_list dhcp.@dnsmasq[0].address="/example.com/192.168.0.1"
# 屏蔽 ad.mi.com 域名的 a 类型解析
# uci add_list dhcp.@dnsmasq[0].address="/ad.mi.com/"
# 生效配置(写入到 /etc/config/dhcp )
uci commit dhcp
# 重启服务
service dnsmasq restart

Ref

Mojang在发布bedrock_server的同时附带上了pdb调试符号文件。

重点是这文件还蛮大的。整个端是100MB,这个调试文件60MB。

不过感觉Mojang这么做大概是故意的,Minecraft是一个商业软件,发不了源代码,但是Minecraft需要社区要做插件,Mojang又懒得做API。

那我给你们调试文件,你们自己反编译去吧。

计划通!

Minecraft Sponge 服务端 Universal Market 插件踩坑记录及修复汉化版本下载

Minecraft 原版玩腻了(龙终于打过了),想玩 Minecraft MOD ,于是乎我装了工业 2 模组。正想着联机,从 mcbbs 里找了半天,感觉靠谱的就没有几个。自己玩又太孤独,那就来搭建一个服吧。这是前言,具体细节不多讲了,总之坑很多,不过好在有前辈们的教程(比如 http://www.mcbbs.net/thread-786074-1-1.html ),路走的还算顺利。本着为人民服务的精神,在这里选取一个坑,总结一下过程,来帮助后来的小伙伴们。

简要介绍

Universal Market 是一个寄售市场,有着类似箱子的界面。

MCBBS 转载贴: http://www.mcbbs.net/thread-792152-1-1.html
Github 原始项目: https://github.com/Xwaffle1/UniversalMarket

下载

20190628 更新:修复了热加载不管用的问题,修复了空手将空气添加到市场的bug

UniversalMarket-1.12.2-v1.3-Bug_fix_and_chinese_translation_by_yys_and_Tollainmear_and_lookas2001.jar

UniversalMarket-master-Bug_fix_and_chinese_translation-source.7z

由于这个项目的各种提示文本是内置在代码里的,所以汉化需要重新编译,上面有项目源代码文件,如果不放心的话,可以按照下方的编译过程自己手动编译。汉化部分采用 Tollainmear 提供的翻译。

出现问题

我搭建的服务器版本为 Minecraft 1.12.2 , Forge 1.12.2-14.23.5.2825 , SpongeForge 1.12.2-2825-7.1.6 。在安装了 1.3 版本的 Universal Market 插件( https://github.com/Xwaffle1/UniversalMarket/releases/tag/1.3 )后发现无法正常进入商店,控制台报错如下:

[xx:xx:xx] [Server thread/ERROR] [Sponge]: Error occurred while executing command 'um' for source EntityPlayerMP['lookas2001'/248, l='world', x=302.00, y=64.00, z=229.00]: There's no NBT Data set in the provided container
org.spongepowered.api.data.persistence.InvalidDataException: There's no NBT Data set in the provided container
    at net.minecraft.item.ItemStack.setRawData(ItemStack.java:2534) ~[aip.class:?]
    at com.xwaffle.universalmarket.utils.ItemBuilder.<init>(ItemBuilder.java:38) ~[ItemBuilder.class:?]
    at com.xwaffle.universalmarket.utils.ItemBuilder.<init>(ItemBuilder.java:31) ~[ItemBuilder.class:?]
    at com.xwaffle.universalmarket.market.Market.openMarket(Market.java:247) ~[Market.class:?]
    at com.xwaffle.universalmarket.market.Market.openMarket(Market.java:167) ~[Market.class:?]
    at com.xwaffle.universalmarket.commands.MarketCommand.process(MarketCommand.java:45) ~[MarketCommand.class:?]
    at org.spongepowered.api.command.dispatcher.SimpleDispatcher.process(SimpleDispatcher.java:340) ~[SimpleDispatcher.class:1.12.2-2825-7.1.6]
    at org.spongepowered.common.command.SpongeCommandManager.process(SpongeCommandManager.java:337) [SpongeCommandManager.class:1.12.2-2825-7.1.6]
    at net.minecraft.command.ServerCommandManager.func_71556_a(SourceFile:1156) [dh.class:?]
    at net.minecraft.network.NetHandlerPlayServer.func_147361_d(NetHandlerPlayServer.java:960) [pa.class:?]
    at net.minecraft.network.NetHandlerPlayServer.func_147354_a(NetHandlerPlayServer.java:939) [pa.class:?]
    at net.minecraft.network.play.client.CPacketChatMessage.func_148833_a(SourceFile:37) [la.class:?]
    at net.minecraft.network.play.client.CPacketChatMessage.func_148833_a(SourceFile:9) [la.class:?]
    at org.spongepowered.common.event.tracking.phase.packet.PacketPhaseUtil.onProcessPacket(PacketPhaseUtil.java:193) [PacketPhaseUtil.class:1.12.2-2825-7.1.6]
    at net.minecraft.network.PacketThreadUtil$1.redirect$onProcessPacket$zlk000(SourceFile:539) [hv$1.class:?]
    at net.minecraft.network.PacketThreadUtil$1.run(SourceFile:13) [hv$1.class:?]
    at java.util.concurrent.Executors$RunnableAdapter.call(Executors.java:511) [?:1.8.0_74]
    at java.util.concurrent.FutureTask.run(FutureTask.java:266) [?:1.8.0_74]
    at net.minecraft.util.Util.func_181617_a(SourceFile:46) [h.class:?]
    at org.spongepowered.common.SpongeImplHooks.onUtilRunTask(SpongeImplHooks.java:307) [SpongeImplHooks.class:1.12.2-2825-7.1.6]
    at net.minecraft.server.MinecraftServer.redirect$onRun$zjo000(MinecraftServer.java:3970) [MinecraftServer.class:?]
    at net.minecraft.server.MinecraftServer.func_71190_q(MinecraftServer.java:723) [MinecraftServer.class:?]
    at net.minecraft.server.dedicated.DedicatedServer.func_71190_q(DedicatedServer.java:397) [nz.class:?]
    at net.minecraft.server.MinecraftServer.func_71217_p(MinecraftServer.java:668) [MinecraftServer.class:?]
    at net.minecraft.server.MinecraftServer.run(MinecraftServer.java:526) [MinecraftServer.class:?]
    at java.lang.Thread.run(Thread.java:745) [?:1.8.0_74]

这时候我有点慌了,因为我之前没有系统的接触过 Java ,只在研究锐捷网络 ESS/SMP 产品授权验证以及 Moegirl Android App 的时候稍微有所了解。

定位和解决

直接上搜索引擎,没找到…

由于这个项目是开源的(Open Source 大法好!),我们可以将代码下载下来慢慢研究。

后来又到原始项目里找 issue 找到了这个 https://github.com/Xwaffle1/UniversalMarket/issues/20 ,通过一些方式联系上了一个已经对前面一个版本的 jar 打完补丁的 dalao Alone,感谢其作品在我没有思路时候对我的启发。

好在有 trace ,我们可以看到最后一个关于这个插件的错误发生在 com.xwaffle.universalmarket.utils.ItemBuilder.<init>(ItemBuilder.java:38) ~[ItemBuilder.class:?] 这里:

我们把 setRawData 这个函数扔到 Sponge Forum 上搜索一下 https://forums.spongepowered.org/t/set-get-modify-subid-of-itemstack/19048/9 ,发现这个函数与在物品上设置一些属性有关,是一个比较 hacky 的做法。

将这段代码对应的函数在项目全局搜索一下:

发现这段代码只跟 Market.java 这个文件相关,打开,查找调用地方。

我们发现实际通过 meta 变量传入设置了 UnsafeDamage (损坏值)的调用点只在这里:

加载了好使的插件后,可以发现这个是支付确认界面的确定按钮。

故推测,这可能是作者想要做的一个类似进度条相关的功能,但是最后可能因为各种原因最后咕咕咕了(人类的本质)。

那就直接把这一行以及相关的两行(即出现 bug 这一行的上面两行)移除掉试一试。

拦路虎——编译

Minecraft 使用 Java 8 作为其运行环境,相应的,其周围 Mod 开发都是在 Java 8 基础上进行的,推荐使用 Java 8 来进行接下来的工作。

我本地用的电脑是 MacBook 开发环境为 MacOS,相对 Windows 系统,在命令行上更加强大一些,周围配套设施也多一些。个人开发的话,平常使用 brew 作为包管理,安装软件快捷迅速。但是 Brew 默认不提供 Java 8 (大概是过时了?),而去 Oracle 官网上下载又是不可能的(下载居然还需要登录),在 StackOverflow 上有这么一个回答 https://stackoverflow.com/a/55774255 ,解决了 Java 8 安装的问题。

看到这个项目使用了 gradle 作为其依赖管理(或者讲构建工具?),依照这我之前用 composer ,npm 的经验,我寻思着应该需要用 brew 安装一下。事实上是不需要的,安装了反而多余。brew 上的 gradle 版本太高,并且项目本身提供了一个包管理命令,即 gradlew 。运行一下会在项目目录以及用户目录生成相应的文件。

于是乎,./gradlew 一下,在下载完必要的文件后,给出了一个提示,按照这个提示,我应该运行 ./gradlew tasks。运行之,找到好像是构建的选项 ./gradlew build 。运行之,傻眼,提示错误:

:compileJava
/xxxxxx/UniversalMarket-master/build/sources/main/java/com/xwaffle/universalmarket/market/Market.java:30: 错误: 程序包org.spongepowered.common.item.inventory.adapter.impl.slots不存在
import org.spongepowered.common.item.inventory.adapter.impl.slots.SlotAdapter;
                                                                 ^
/xxxxxx/UniversalMarket-master/build/sources/main/java/com/xwaffle/universalmarket/market/Market.java:31: 错误: 程序包org.spongepowered.common.item.inventory.query.operation不存在
import org.spongepowered.common.item.inventory.query.operation.InventoryPropertyQueryOperation;
                                                              ^
/xxxxxx/UniversalMarket-master/build/sources/main/java/com/xwaffle/universalmarket/market/Market.java:32: 错误: 程序包org.spongepowered.common.item.inventory.util不存在
import org.spongepowered.common.item.inventory.util.ItemStackUtil;
                                                   ^
/xxxxxx/UniversalMarket-master/build/sources/main/java/com/xwaffle/universalmarket/market/MarketItem.java:10: 错误: 程序包org.spongepowered.common.item.inventory.util不存在
import org.spongepowered.common.item.inventory.util.ItemStackUtil;
                                                   ^
/xxxxxx/UniversalMarket-master/build/sources/main/java/com/xwaffle/universalmarket/utils/ItemBuilder.java:11: 错误: 程序包org.spongepowered.common.item.inventory.util不存在
import org.spongepowered.common.item.inventory.util.ItemStackUtil;
                                                   ^
注: Writing plugin metadata to file:/xxxxxx/UniversalMarket-master/build/classes/main/mcmod.info
5 个错误
:compileJava FAILED

FAILURE: Build failed with an exception.

* What went wrong:
Execution failed for task ':compileJava'.
> Compilation failed; see the compiler error output for details.

* Try:
Run with --stacktrace option to get the stack trace. Run with --info or --debug option to get more log output.

BUILD FAILED

翻找 Sponge 文档,看到官方给出的例子都是基于 IDE 的,但是由于我的 MacBook 空间不够,最后在另外一台电脑上(Windows)安装了Intellij IDEA Community ,然后使用 IDE 提供的构建按钮,又花费了很长的一段时间下载,最后提示了两个错误 “PKIX path building failed” 和 “unable to find valid certification path to requested target” (在 Windows 上使用命令构建不会出现这个问题,但是仍然会出现上述在 MacOS 已经出现的错误),看来不是 IDE 的问题,返回我的 MacBook 。

在前一个步骤中,我观察到了一个事情,为什么其他引入不会出现问题,而这些引入会出现问题,我发现这些包都是以 org.spongepowered.common.xxxx 开头。之前有查看过 build.gradle 这个文件,明明有通过 compile 'org.spongepowered:spongeapi:7.0.0' 引入 SpongeAPI 。在是 IDE 的问题排查完后,我决定去看看 Java 编译器到底在引入一些什么东西。

由于之前有过 gradle 相关的经历,知道 gradle 会在用户目录生成文件夹 ~/.gradle ,去之,然后搜索之 find . | grep sponge 。搜索结果中有一个 ./caches/modules-2/files-2.1/org.spongepowered/spongeapi/7.0.0/ada1f9981de3459b182ee16d6408173ef33a8943/spongeapi-7.0.0.jar 这一看就是 api 对应的包嘛。

解压之(反编译就不用了):

自闭了

哪来的 common 啊!!

回到 build.gradle 目光下移一行,compile files('libs/spongeforge-1.12.2-2555-7.1.0-BETA-2837.jar') 在结合 SpongeCommon 项目的描述,这作者 tm 直接把 SpongeForge 的发布版本当做依赖了啊!而且源代码还把这个目录给删了!!!结合利用偏门 API 的事情来看(Sponge 不推荐插件作者绕过 Sponge 等行为,这个插件作者直接引入了 net.minecraft.nbt.NBTTagCompound),怪不得这个作者在发布 MOD 没在 Ore 上发啊(可能也跟 Sponge 没提供一些 API 有关)。

下载了现在最新的稳定版本 SpongeForge (spongeforge-1.12.2-2825-7.1.6.jar)(老的不想往后翻了),创建 libs 目录扔进去。然后修改一下 build.gradle 里对应的文件名(保持匹配)。再运行一下 ./gradlew build

小宝贝,终于看见你了:

最后经过测试,工作完美。

OpenWrt 上通过 WebDAV 共享文件

lookas2001 版权所有,本作品采用知识共享署名 4.0 国际许可协议进行许可,转载使用的时候请注明作者以及来源。

OpenWrt ( https://openwrt.org/ ) 是一个蛮强大的路由器固件,通过安装软件包可以实现很多功能。WebDAV ( http://www.webdav.org/ ) 是一个对 HTTP 的拓展,可用于共享文件。于是乎,我们可以尝试在 OpenWrt 上安装相应的软件包,让设备支持 WebDAV。

相比于 SMB, AFP,在实际测试中,WebDAV 的速度比较占优势。这点可能得益于 WebDAV 是基于 HTTP 的,HTTP 服务端可能有一些黑科技在降低占用的时候提高速度(也有可能是接下来的步骤中的 WebDAV 是基于 http 而不是 https 的原因)。

另外写这一篇文章的原因是 SMB 和 AFP 已经有了比较完善的教程,比如这两篇文章 https://openwrt.org/docs/guide-user/services/nas/samba_configuration https://openwrt.org/docs/guide-user/services/nas/netatalk_configuration 但是 WebDAV 在文档方面就比较缺乏。

Lighttpd ( https://www.lighttpd.net/ ) 是一个轻量级的,但是功能较为完备的 HTTP 服务端,观察到他提供了 WebDAV mod ,故可用其来实现 WebDAV 服务器。

安装 Lighttpd 以及 WebDAV Auth 模块

opkg update 来更新本地的软件包信息。

通过 opkg install lighttpd lighttpd-mod-webdav lighttpd-mod-auth lighttpd-mod-authn_file 可将所依赖的软件包一键装齐。

如果出现了下载速度慢或者下载遇到困难,可以手动到 http://downloads.openwrt.org 上下载对应的包然后安装,或者设置一下网络代理(这不属于这篇文章的谈论范围,需要你自己想办法啦)。

配置 Lighttpd

不像 SMB 提供了 uci 统一配置的接口,Lighttpd 需要在 /etc/lighttpd 下修改。

通过 vi /etc/lighttpd/lighttpd.conf 打开 lighttpd 的主配置文件。

可通过 cp /etc/lighttpd/lighttpd.conf /etc/lighttpd/lighttpd.conf.bak 设置一个备份,便于配置出错的时候还原。

这是一份配置过的配置文件:

server.document-root        = "/mnt"
server.upload-dirs          = ( "/tmp" )
server.errorlog             = "/var/log/lighttpd/error.log"
server.pid-file             = "/var/run/lighttpd.pid"
server.username             = "http"
server.groupname            = "www-data"

index-file.names            = ( "index.php", "index.html",
                                "index.htm", "default.htm",
                              )

static-file.exclude-extensions = ( ".php", ".pl", ".fcgi" )

### Options that are useful but not always necessary:
#server.chroot               = "/"
server.port                 = 81
#server.bind                 = "localhost"
#server.tag                  = "lighttpd"
server.errorlog-use-syslog  = "enable"
#server.network-backend      = "writev"

### Use IPv6 if available
#include_shell "/usr/share/lighttpd/use-ipv6.pl"

dir-listing.encoding        = "utf-8"
server.dir-listing          = "enable"

include "/etc/lighttpd/mime.conf"
include "/etc/lighttpd/conf.d/*.conf"

lighttpd 配置文件中注释是通过在行前加入“#”来实现的。

这里修改了几点:

server.document-root = "/mnt" ,即将文档根目录设置为 /mnt ,我为路由器添加了两个硬盘,分别挂载在 /mnt/sda1 和 /mnt/sdb1 下,这个存放位置不是固定的,可以根据你自己的喜好调整。

server.port = 81 ,即后面我们用来访问的端口,80 端口已经被系统自带的 uHTTPd 占用了,这里设置另外一个防止冲突。

server.errorlog-use-syslog = "enable" ,这个选项可以将错误日志输出到 syslog ,便于我们在 web 控制台查看错误。

server.dir-listing = "enable" , dir-listing.encoding = "utf-8" ,这两个选项可以启用列出文件功能,并且防止文件名乱码。

配置 WebDAV 模块

通过 vi /etc/lighttpd/conf.d/30-webdav.conf 打开 lighttpd 的主配置文件。

这是一份配置过的配置文件:

#######################################################################
##
##  WebDAV Module
## ---------------
##
## See https://redmine.lighttpd.net/projects/lighttpd/wiki/Docs_ModWebDAV
##
server.modules += ( "mod_webdav" )

#$HTTP["url"] =~ "^/dav($|/)" {
  ##
  ## enable webdav for this location
  ##
  webdav.activate = "enable"

  ##
  ## By default the webdav url is writable.
  ## Uncomment the following line if you want to make it readonly.
  ##
  webdav.is-readonly = "enable"

  ##
  ## Log the XML Request bodies for debugging
  ##
  #webdav.log-xml = "disable"

  ##
  ##
  ##
  webdav.sqlite-db-name = "/tmp/lighttpd-webdav.db"
#}
##
#######################################################################

这里修改了几点:

注释掉了 $HTTP["url"] =~ "^/dav($|/)" { , } 两行,这里安装 Lighttpd 的目的就是为了 WebDAV ,注释掉这两行可以将整个网站都设置为 WebDAV 。

webdav.activate = "enable" ,为整个站点启用了 WebDAV 。

webdav.is-readonly = "enable" ,设置运行模式是只读模式,这里设置 disable 可以禁用只读(即可写可读)。

"/mnt/sda1/.lighttpd-webdav.db" ,这里需要为 WebDAV 模块设置一个数据库存储位置,位置建议选择在硬盘上,这个数据库文件需要存储的除了锁定还有一些属性,如果存储在易丢失的地方(如 /tmp )会导致数据丢失,存储上除硬盘以外的位置会缩短闪存寿命(闪存有擦除上限),请注意,Lighttpd 需要对存储位置的目录有写入的权限,可用 chmod a+w xxx,来授予权限。

Ref

  • OpenWrt 论坛上的内容 https://forum.openwrt.org/t/webdav-configuration-essense-with-lighttpd-on-openwrt/25357
  • Lighttpd 提供的文档 https://redmine.lighttpd.net/projects/lighttpd/wiki/Docs_ModWebDAV

配置 Auth 模块

这块的配置是用于提升你的文件安全性的,但并不是必须的,而且这方面的配置只可提升少许安全性,攻击者仍然可以在中途截获密码,若想更好的提升安全性,请配置 HTTPS 。

通过 vi /etc/lighttpd/conf.d/20-auth.conf 打开 lighttpd 的主配置文件。

这是一份配置过的配置文件:

#######################################################################
##
##  Authentication Module
## -----------------------
##
## See https://redmine.lighttpd.net/projects/lighttpd/wiki/docs_modauth
## for more info.
##
server.modules += ( "mod_auth" )

auth.backend                 = "plain"
auth.backend.plain.userfile  = "/etc/lighttpd/lighttpd.user"
#auth.backend.plain.groupfile = "/etc/lighttpd/lighttpd.group"

#auth.backend.ldap.hostname = "localhost"
#auth.backend.ldap.base-dn  = "dc=my-domain,dc=com"
#auth.backend.ldap.filter   = "(uid=$)"

auth.require               = ( "/" =>
                               (
                                 "method"  => "basic",
                                 "realm"   => "Personal File Server",
                                 "require" => "valid-user"
                               ),
                             )

##
#######################################################################

这里修改了几点:

可能是包打包人员的疏忽,原来的配置文件中没有 server.modules += ( "mod_auth" ) 一行,为了启用这个模块,须有手动加上。

auth.backend = "plain" ,设置认证后端为 plain

auth.backend.plain.userfile = "/etc/lighttpd/lighttpd.user" ,设置认证后端存储认证信息的位置。

auth.require = ..... ,取消这里的注释即意味着启用了认证。

"/" ,代表认证的位置,这里是全站。

"method" => "basic" ,认证的类型,这里设置为 basic 是为了更好的客户端兼容性。

"realm" => "Personal File Server" ,即认证时提示的消息,随便设置即可。

通过 touch /etc/lighttpd/lighttpd.user 可以创建我们需要的认证信息文件。

通过 vi /etc/lighttpd/lighttpd.user 编辑认证信息文件。

这是一份样例:

user1:password1
user2:password2

用户名和密码见用 : 隔开,多个用户之间用空行隔开。

Ref

  • Lighttpd 提供的文档 https://redmine.lighttpd.net/projects/lighttpd/wiki/docs_modauth

Min_25 筛学习笔记(伪)

推荐博客: https://blog.csdn.net/qq_33229466/article/details/79679027

下面口胡,一些犄角旮旯地方的理解。

将所有数做质因数分解,考虑将数按照第一个质因子及其次数(即 p^e)分类,我们发现由于积性函数的性质,这一类的和可以共同提取出一个 f(p^e) ,即式子会变成 f(p^e)(f(a_1 / p^e) + f(a_2 / p^e) + …) 。可以发现式子的后半部分就是一个很类似的问题。这大概就是 Min_25 筛的主要思想吧。

具体来讲是定义了两个求和函数,其中一个求和函数(即朱震霆论文中的 h ,网上大多数博客的 g)辅助另外一个求和函数(即朱震霆论文中的 g ,网上大多数博客的 S)求值。

那个辅助求值函数的求值过程非常类似埃氏筛的过程,故这个方法也称拓展埃氏筛法。

空间使用只需要 O(\sqrt n) ,因为每次递归形如(都是向下取整的除法) n -> n / i , n / i -> n / i / j ,而 n / i / j 可以等价为 n / (i * j) 。数论分块,下略。

复杂度啥的见朱震霆的论文吧。

下面是一些(应该没有锅的)数学公式,代码直接套这些公式就好了,模板在 Counting Divisors 。

积性函数: $f(x)$

要求有 $f(p^e) = \sum_k a_k(e)p^k$ 。

辅助求和函数: $h_k(n, j) = \sum_{2 \leq i \leq n 且 (i 的最小质因子 > p_j 或 i 是质数)} i^k$

若 $p_j > \sqrt n$ ,有 $h_k(n, j) = h_k(n, j – 1)$ ;

否则,有 $h_k(n, j) = h_k(n, j – 1) – p_j^k(h_k(\lfloor \frac n{p_j}\rfloor, j – 1) – h_k(p_j – 1, j – 1))$ 。

特别的,对于 $j = 0$ ,有 $h_k(n, j) = \sum_{2 \leq i \leq n} i^k$ 。

简记 $h_k(n) = h_k(n, j)$ 其中 $p_j > \sqrt n$ (即我们要的辅助求和函数最后没有合数项的)。

求和函数: $g(n, m) = \sum_{2 \leq i \leq n 且 (i 的最小质因子 > p_m)} f(i)$

可知 $g(n, m) = \sum_k a_k(1)(h(n) – h(p_m)) + \sum_{p_m < p_j\leq \sqrt n 且 e \geq 1 且 p_j^{e + 1} \leq n} (f(p_j^e) g(\lfloor \frac n{p_j^e}\rfloor, j) + f(p_j^{e + 1}))$

$p_0$ 的话当 $0$ 处理就好咯。

$g(n, 0)$ 即为所求。

#include <cstdio>
#include <cstring>

typedef unsigned long long u64;

const int MAX_SQRT_N = 1e5;

struct euler_sieve {
    static const int MAX_N = MAX_SQRT_N;
    bool f[MAX_N + 10];
    int p[MAX_N + 10];
    int p_n;

    inline void operator()(int n) {
        memset(f, 0, sizeof f);
        p_n = 0;
        for (int i = 2; i <= n; ++i) {
            if (!f[i]) {
                p[++p_n] = i;
            }
            for (int j = 1; p[j] * i <= n; ++j) {
                f[p[j] * i] = true;
                if (i % p[j] == 0) break;
            }
        }
    }
} es;

struct Min_25_sieve {
    u64 n;

    u64 b[2 * MAX_SQRT_N + 10]; // 所有可能的 n / i 值,值是从大到小的(废话)
    int b_n, sqrt_n;
    inline int locate(u64 i) { return i < sqrt_n ? b_n - i + 1 : n / i; } // 查找 b[j] == i 的位置 j 

    int d0[2 * MAX_SQRT_N + 10]; // 存储 h 函数的值,数组命名个人癖好而已。 h 函数的取值只有 O(\sqrt n) 种。这里的第 i 个位置存储的不是 h(i) 而是 h(b[i])
    inline void pre_calc() { // 计算 h 函数
        for (int i = 1; i <= b_n; ++i) d0[i] = 1 * (b[i] - 1); // h(b[i], 0) ,j = 0 理解为没有“i 的最小质因子 > p_j”这条限制即可。这里以及下面的 1 * 代表的就是 i^k (本题中 k = 0(不是输入的那个 k 啊))
        for (int j = 1; (u64)es.p[j] * es.p[j] <= n; ++j) { // 枚举质数
            for (int i = 1; (u64)es.p[j] * es.p[j] <= b[i]; ++i) { // 枚举了有用的,即 b[i] 
                d0[i] = d0[i] - 1 * (d0[locate(b[i] / es.p[j])] - d0[locate(es.p[j] - 1)]); // 一定有 p[j] - 1 < \sqrt n ,所以一定可以找到一个合法的位置(不会落在一个段内) // 由于 b[i] 的值是从大道小的,所以求值顺序是没有问题的,不用开另外一个缓存数组
            }
        }
    }

    u64 f_a0_k;
    inline u64 f_a0(int e) { return e * f_a0_k + 1; }
    inline u64 f(int p, int e) { return f_a0(e); }

    u64 calc(u64 n, int m) { // 计算 g 函数
        u64 rst = f_a0(1) * (d0[locate(n)] - d0[locate(es.p[m])]);
        for (int j = m + 1; (u64)es.p[j] * es.p[j] <= n; ++j) {
            u64 pe = es.p[j];
            for (int e = 1; (u64)pe * es.p[j] <= n; ++e, pe *= es.p[j]) {
                rst += f(es.p[j], e) * calc(n / pe, j) + f(es.p[j], e + 1);
            }
        }
        return rst;
    }

    inline u64 operator()(u64 n_, u64 f_a0_k_) {
        n = n_;
        f_a0_k = f_a0_k_;

        // 分块
        sqrt_n = 0; while ((u64)sqrt_n * sqrt_n < n) ++sqrt_n;
        b_n = 0; for (u64 i = 1; i <= n; i = n / (n / i) + 1) b[++b_n] = n / i;

        // 处理辅助求和函数
        pre_calc();

        // 求和
        es.p[0] = 0, d0[b_n + 1] = 0;
        return calc(n, 0) + 1; // + 1 是那个甩单的 1 
    }
} mns;

int main() {
    // freopen("in.in", "r", stdin);

    int tc; scanf("%d", &tc);
    // int tc = 1;
    es(MAX_SQRT_N + 5); // 筛出质数
    while (tc--) {
        u64 n, f_a0_k; scanf("%llu%llu", &n, &f_a0_k);
        printf("%llu\n", mns(n, f_a0_k));
    }

    return 0;
}

要结束了啊

要结束了啊。

NOIP 2018 394 分,当时无知的我还认为这个分数可以,殊不知强省们的选手早已在 500 分以外。不,其实我知道,只是我不愿意承认呐。3 年的时光被我荒废掉了,1 年的时间我依然没有紧紧抓住。到现在了,一切,都马上要结束了。

没有清华北大冬令营的邀请,对于我,如果想要通过竞赛的道路去到清华北大,剩下的,只有 NOI 金牌了啊。

但是,没有但是啊。自己的水平怎么可能会在接下来那仅仅 6 个月内赶上比我领先了太多太多了的人呢?

怎么会呢?

那就让一切结束了吧。

1 月 24 日的 CCF 冬令营,这会是我最后一次考试。在广二这个学校,第一次,也是最后一次了。

祝福,祝福跟我一路走来的同学们。

祝你们能在 2019 年的 NOI 的赛场上取得一个好的成绩,路上小心,加油!

感谢,感谢一路上支持我一步一步走过来的老师、家长们。

虽然没有让你们见到我在 NOI 赛场上的那一刻,但是我这长又短的 OI 生涯中,你们给予了我知识,最重要的还有温暖与陪伴。

愿我们来年有幸再会。

lookas2001

1 月 6 日 于广州

NOIP 2018 游记

变化,这是我对今年 NOIP 的概括,从天津赛区的选址变为新校区,到 CCF 更新那个被无数选手诟病已久的“老爷机”,可以看出来 NOIP 的不断完善以及受重视程度不断提高。废话不多说,谈谈本次考试的想法吧。

Day 1

第一题铺设道路,一道简单的贪心,随便打个树状数组 30min A 掉切下一题(其实时间要比 30 分钟长)。

看到了第二题,艹,数学题,还是去年小凯的疑惑加强版。不过简单的分析一下可以发现如果一个数能被其他数表示,那么这个数字一定是没用的,否则是一定是有用的(“显然”),手玩了几组样例,发现思路正确,然后打了一个筛,1h A 掉完事切下一道题。这里的筛有一个坑,就像欧拉筛一样,必须做一个标记,否则复杂度无法保证那就妥妥的 T 了。

然后去厕所呼吸一下新鲜空气,大概 2.5h 过去了。

看第三题,读了两遍题发现是树形动态规划,可惜我的树形动态规划是上周学的,敲掉暴力,写个对拍,弄几组测试数据测试一下,交卷。

今年 Day 1 的题目看网上的说法是都撞题了,不过可惜我都没做过(zg dalao 两个月 A 掉 300 道题目 %%% 啊)。

Day 2

读了一遍题,发现第一题的数据特别神奇,是一个单环树,考虑断环上边然后枚举去做,这样复杂度已经 O(n^2) 了,可是还要求最小,所以考场上的想法就是每次都排一遍序,O(n^2logn) ,考虑到今年 CCF 换评测机,外加由于每次排序改变的东西并不会非常多,所以就这样了,没有细想。好在命大,最后拜托了我“优秀”的卡常技巧,居然卡过去了。具体来讲用 vector 存边的都 T 了…

第二题,艹,又是数学题,不过由于心太高,所以在这道题上犯了一个考场上一定不能犯的错误,就是硬抗,事实证明,要不是我福大命大,最后 30 分钟 T3 调出来了,否则就凉凉了,这道题目浪费了我足足 1 个小时,不过最后还是果断换题了,减少损失,最后一道题目敲出来了以后回来发现有几组白痴数据,手敲了一个表,交了上去,最后在基础的暴力分上只扣了 5 分,感谢 CCF 弱数据…

第三题,这是 NOI Plus 吧…不会,敲了一个暴力交了上去。

总结

总体来讲体验还算可以,但是之前犯的错,这次又犯了,时间规划真的非常非常非常重要啊!

另外感觉这次比赛自己的码风非常吃亏,因为我一直坚持的代码可读性原则导致我的代码普遍比别人长 2 倍以上,这个可能要改一下了,毕竟打的是竞争性的比赛,而不是长久维护的工程。

394,近 400 分的成绩对的起我一年的付出,我已经非常满意了。

NOI 2019 我们明年见!

图为 NOIP 2018 天津考场,天津大学北洋园校区。

奋斗!

午后,阳光射进自习室,温暖而不刺眼。与那些进队的物理化学同学们坐在一个地方,一同为这自己的目标奋斗,这大概是人生最好的时刻了吧。

但是,我跟他们不一样,我只有这一次机会了。成还是败,就在这一举了。

我不是一个普通的孩子,我一定会做出自己的事业。这是我一直告诉我自己的,过去是,现在是,将来更是。

加油,抓紧每一分时间,奋斗!

理想与现实

一堆课文没背,一堆事情没办,今天过的又很让人沮丧。

其实,你们知道吗,我知道为什么吾得这个项目为什么4年了到现在都没有什么特别大的进展了。大概是我过于理想化了,我给吾得打上了太多的标签,就像父亲对孩子,有过多的想法,我没有找到重点,这样导致我没办法实现。其实这也有一部分是我的行动力的问题,我错在全在想而不是在做,一直都是TODO而不是Do。

吾得是我对有一定成就的愿望的寄托,或者说是,我希望成为一个像一些名人一样受人尊重,敬仰,但是我错了。我一直在说的是人权,保护个人隐私,但是如果我忽然有了权力,有了地位了,我还会这么想吗?我在保护我个人的隐私的同时,我在干什么,我爬了别人的成绩窥探了他人的隐私。我的呼吁是没有力度的。更令人无语的是,我希望他人去跟从我的想法而我却不愿意承认他人的爱好。这是一种病态的思维方式。

话又说回来,为什么我今天心情又不好了?人类是一个很神奇的动物,总是会对一些东西抱有不切实际的期望。其实我已经很不错了,但是我在想变得更好,但是我却不想为此付出代价,这很可笑对吧,但是的确是我的现状,我需要去改变。

我需要改变,但是我也迷茫,我该改变成什么样子,下一步,我该何去,又该何从?希望几年后的我看到这些文字的时候不会是一个颓丧的样子。Fighting!