题目 Lcm(a,b)表示a和b的最小公倍数，A(n)表示Lcm(n,i)的平均数(1 <= i <= n)，
例如：A(4) = (Lcm(1,4) + Lcm(2,4) + Lcm(3,4) + Lcm(4,4)) / 4 = (4 + 4 + 12 + 4) / 4 = 6。
F(a, b) = A(a) + A(a + 1) + ...... A(b)。(F(a,b) = ∑A(k), a <= k <= b)
例如：F(2, 4) = A(2) + A(3) + A(4) = 2 + 4 + 6 = 12。
给出a,b，计算F(a, b)，由于结果可能很大，输出F(a, b) % 1000000007的结果即可。
收起
输入
输入2个数a,b，中间用空格分隔(1 <= a <= b <= 10^9)。
输出
输出F(a, b) % 1000000007的结果。
输入样例
1 100
输出样例
122726
解题思路:对于A(n)可以得到,
文章图片
。设A的前缀和为B，那么
文章图片
又因为
文章图片
所以
文章图片
,设
文章图片
,很明显F(i)是积性函数，那么如果我们可以快速求出F(i)的前缀和，就可以在
文章图片
时间内求出B(n)了。求积性函数前缀和很容易想到杜教筛，
【数论|51nod1227 平均最小公倍数(杜教筛)】那么
文章图片
，
因此F(i)的前缀和
文章图片
。答案即为B(b)-B(a-1)。
代码:
#include
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
const int inv6 = 166666668;
const int inv2 = 5e8 + 4;
map M;
int prime[maxn],mark[maxn];
ll phi[maxn];
void gettable(){
phi[1] = 1;
for(int i = 2;
i < maxn;
++i){
if(!mark[i]) prime[++prime[0]] = i,phi[i] = i - 1;
for(int j = 1;
j <= prime[0] && i * prime[j] < maxn;
++j){
mark[i * prime[j]] = 1;
if(i % prime[j] == 0){
phi[i * prime[j]] = phi[i] * prime[j];
break;
}
phi[i * prime[j]] = phi[i] * (prime[j] - 1);
}
}
for(int i = 2;
i < maxn;
++i) phi[i] = (phi[i - 1] + phi[i] * i % mod) % mod;
}ll getsum(ll n){
if(n < maxn) return phi[n];
if(M[n]) return M[n];
ll sum = n * ((2 * n + 1) % mod) % mod * (n + 1) % mod * inv6 % mod,k;
//n*(2*n+1)*(n+1)/6
for(ll i = 2;
i <= n;
i = k + 1){
k = n / (n / i);
sum = (sum - getsum(n / i) * (i + k) % mod * (k - i + 1) % mod * inv2 % mod)% mod;
}
return M[n] = (sum + mod) % mod;
}ll cal(ll n){
ll res = n,k;
for(ll d = 1;
d <= n;
d = k + 1){
k = n / (n / d);
res = (res + getsum(n / d) * (k - d + 1) % mod) % mod;
}
return res * inv2 % mod;
}int main(){
gettable();
ll a,b;
cin>>a>>b;
cout<<(cal(b) - cal(a - 1) + mod) % mod < 推荐阅读
- 数据结构和算法|LeetCode 的正确使用方式
- #|7.分布式事务管理
- #|算法设计与分析（Java实现）——贪心算法（集合覆盖案例）
- #|算法设计与分析（Java实现）—— 动态规划 （0-1 背包问题）
- #|阿尔法点亮LED灯(一）汇编语言
- #|Multimedia
- #|ARM裸机开发（汇编LED灯实验（I.MX6UL芯片））
- 基础课|使用深度优先搜索（DFS）、广度优先搜索（BFS）、A* 搜索算法求解 (n^2 -1) 数码难题，耗时与内存占用（时空复杂度）对比（附（(n^2 - 1) 数码问题控
- #|学习笔记 | Ch05 Pandas数据清洗 —— 缺失值、重复值、异常值
- win10|搏一搏 单车变摩托，是时候捣鼓一下家中的小米电视机啦。