#1436. 简单的函数 10^13 版

简单的函数 10^13 版

题目描述

很久以前的某一天,你发现了一个神奇的函数 f(x)f(x),它满足很多神奇的性质:

  1. f(1)=1f(1)=1
  2. f(pc)=pcf(p^c)=p \oplus cpp 为质数,\oplus 表示异或)。
  3. f(ab)=f(a)f(b)f(ab)=f(a)f(b)aabb 互质)。

S(m)=i=1mf(i)mod(109+7)S(m)=\sum\limits_{i=1}^m f(i) \bmod (10^9+7),你需要对于 i=1,2,3,,ni=1,2,3,\cdots,n 求出 S(n/i)S(\lfloor n/i\rfloor),去重并输出异或和。

输入格式

一行一个正整数 nn

输出格式

一行一个非负整数,表示去重后的 {S(n/i)}i[1,n]\left\{S(\lfloor n/i\rfloor)\right\}_{i\in[1,n]} 的异或和。

样例 1

6
19

去重后的集合为 {1,4,6,16}\{1,4,6,16\},异或和为 1919

233333
354637812
9876543210
926874502
98765454321
371750957

数据范围与提示

对于 20%20\% 的数据,n106n \leq 10^6
对于 40%40\% 的数据,n109n \leq 10^9
对于 60%60\% 的数据,n1010n \leq 10^{10}
对于 80%80\% 的数据,n1011n \leq 10^{11}
对于 90%90\% 的数据,n1012n \leq 10^{12}
对于 100%100\% 的数据,1n10131 \leq n \leq 10^{13}

基于 https://loj.ac/p/6783。