#P4176. [2015年湖南省队省队集训]Lucas的数论

    ID: 3394 传统题 2000ms 256MiB 尝试: 792 已通过: 298 难度: 8 上传者: 标签>CF2500提高+/省选-莫比乌斯函数交换求和顺序整除分块杜教筛线性筛记忆化搜索

[2015年湖南省队省队集训]Lucas的数论

题目描述

去年的Lucas非常喜欢数论题,但是一年以后的Lucas却不那么喜欢了。

在整理以前的试题时,发现了这样一道题目“求Sigma(f(i)),其中1≤i≤n1 \le i \le n”,其中表示i的约数个数。他现在长大了,题目也变难了。

求如下表达式的值:

∑i=1n∑j=1nf(ij)\sum_{i=1}^n \sum_{j=1}^n f(ij)

其中 f(ij)f(ij) 表示 ijij 的约数个数。 他发现答案有点大,只需要输出模 10000000071000000007 的值。

输入格式

第一行一个整数 nn。

输出格式

 一行一个整数 ansans,表示答案模 10000000071000000007 的值。

2
8

提示

 对于100%的数据 n≤109n \le 10^9。

题目来源

没有写明来源