luogu#P11417. [Sloi 2024] D1T1 精卫

    ID: 35317 远端评测题 800ms 50MiB 尝试: 0 已通过: 0 难度: 5 上传者: 标签>数论深度优先搜索 DFS素数判断,质数,筛法

[Sloi 2024] D1T1 精卫

题目背景

题目描述

f(x)f(x) 为积性函数,且满足 f(pk)=p2k+kf(p^k)=p^{2k}+kpp 为素数)。

令 $g(x)=\prod\limits_{d|x}f(d)\space \bmod\space (10^9+7)$ ,请计算 g(i) (1in)g(i)\space (1\le i \le n) 的异或和。

输入格式

一行一个正整数 nn

输出格式

一行一个非负整数。

5
78
142857
67850062
10000000
505679580

提示

本题采用捆绑测试

Subtask n Score
11 104\le10^4 1010
22 5×106\le 5\times 10^6 3030
33 2×107\le 2\times 10^7
44 5×107\le 5\times10^7

100%100\% 的数据,1n5×1071\le n \le 5\times10^{7}