lookas2001

之前在接触到多播这个概念的时候一直在想这么美好的东西为什么不在互联网上使用，后来想了想，现在一直在说的 CDN 不就是做到这一点了嘛，减少骨干网络上重复数据的传输，在近用户端复制成多份分发。

今天看到腾讯云的这个演讲，同时也印证了这个观点：腾讯云PCDN：从P2P到万物互联框架

另外，P2P真的是一个很有趣的东西，与人斗，其乐无穷~

永远不要对他人的不幸落井下石，因为你无法确保你自己不会遇到类似情况。

Web 本质就是一个传递信息的工具，Web 有着用于传递信息的方法 HTTP，Web 有着用于表示信息的方法 HTML，那 Web 2.0 到底特殊在哪里？

我的理解， Web 2.0 将如何传递信息以及如何表达信息与用户的使用做了隔离，也就是说，在Web 2.0 时代，用户没有必要去考虑如何做出一个美观的网页，如何将自己的信息一直放在网上，如何用flash嵌入自己的视频作品，他只需要去做的是写一段文字，或者上传一些视频，其余的内容由计算机城区去帮忙处理。

Web 2.0 使得互联网的分工进行了细化，界面的美观设计有专业的设计师去处理，信息的保存有专门的运维去处理，解决各种疑难问题有程序员去做等等。

Web 2.0 其实就是应用程序这个概念的互联网延伸。

Web 2.0 的特性导致为了完成上述事宜，以及某些决策人员恬不知耻的产品“护城墙”战略，导致了互联网的中心化，从互联网变成了互联树，让用户的信息成为了一些公司的摇钱树，以及让控制信息的传播成为了[censered]。

将程序与数据分开吧！去掉那些本来就没有必要存在的中心化节点吧！还网络一个自由、开放的世界吧！

#拥抱IPFS ~~hashtag…~~

有些时候，我们可能希望屏蔽一个网站（例如：屏蔽小米广告），或者为特定的网站设置一个解析（例如：自己网站发布前在本地进行测试）。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

• https://openwrt.org/docs/guide-user/base-system/dhcp_configuration#domains OpenWrt.org 上提供的样例（其他类型解析什么的）

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

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

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

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

计划通！

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

小宝贝，终于看见你了：

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

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

推荐博客： 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 日 于广州