【学术篇】51nod 1238 最小公倍数之和

时间:2022-08-31 23:45:32

这是一道杜教筛的入(du)门(liu)题目...


题目大意

\[\sum_{i=1}^n\sum_{j=1}^nlcm(i,j)
\]

一看就是辣鸡反演一类的题目, 那就化式子呗..

\[\sum_{i=1}^n\sum_{j=1}^nlcm(i,j) \\
=\sum_{i=1}^n\sum_{j=1}^n\frac{ij}{gcd(i,j)} \\
=\sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^n\frac{ij}k[gcd(i,j)=k] \\
=\sum_{k=1}^n\sum_{i=1}^{\left\lfloor\frac nk\right\rfloor}\sum_{j=1}^{\left\lfloor\frac nk\right\rfloor}ijk[gcd(i,j)=1] \\
=\sum_{k=1}^nk\sum_{i=1}^{\left\lfloor\frac nk\right\rfloor}i\sum_{j=1}^{\left\lfloor\frac nk\right\rfloor}j[gcd(i,j)=1] \\
=\sum_{k=1}^nk\sum_{i=1}^{\left\lfloor\frac nk\right\rfloor}i\sum_{j=1}^{\left\lfloor\frac nk\right\rfloor}j\sum_{d=1}^{\left\lfloor\frac nk\right\rfloor}[d|i][d|j]\mu(d) \\
=\sum_{k=1}^nk\sum_{d=1}^{\left\lfloor\frac nk\right\rfloor}\mu(d) \sum_{i=1}^{\left\lfloor\frac nk\right\rfloor}[d|i]i \sum_{j=1}^{\left\lfloor\frac nk\right\rfloor}[d|j]j \\
设i=dq,j=dq, \\
原式=\sum_{k=1}^nk\sum_{d=1}^{\left\lfloor\frac nk\right\rfloor}\mu(d) \sum_{p=1}^{\left\lfloor\frac nk\right\rfloor}dp \sum_{q=1}^{\left\lfloor\frac nk\right\rfloor}dq \\
=\sum_{k=1}^nk\sum_{d=1}^{\left\lfloor\frac nk\right\rfloor}\mu(d)*d^2\sum_{p=1}^{\left\lfloor\frac nk\right\rfloor}p \sum_{q=1}^{\left\lfloor\frac nk\right\rfloor}q \\
\because\sum_{i=1}^ni=\frac{n(n+1)}2, \\
\therefore原式=\sum_{k=1}^nk\sum_{d=1}^{\left\lfloor\frac nk\right\rfloor}\mu(d)*d^2(\frac{{\left\lfloor\frac nk\right\rfloor}({\left\lfloor\frac nk\right\rfloor}+1)}{2})^2 \\
设t=kd, \\
原式=\sum_{t=1}^n(\frac{{\left\lfloor\frac nt\right\rfloor}({\left\lfloor\frac nt\right\rfloor}+1)}{2})^2\sum_{d|t}\mu(d)*td \\
设g(x)=\sum_{d|x}\mu(d)*xd, \\
则原式=\sum_{t=1}^n(\frac{{\left\lfloor\frac nt\right\rfloor}({\left\lfloor\frac nt\right\rfloor}+1)}{2})^2g(t)
\]

然后前面这一堆我们可以分块\(O(1)\)搞出来, 所以问题的关键就变成了求\(g(x)\)的前缀和.

因为题目中\(n\leq10^{10}\), 所以这里要用\(O(n^\frac23)\)的杜教筛.

但是杜教筛的框架我们是知道的,

\[设要求前缀和的函数为f(x), 其前缀和为s_f(x) \\
设有好求前缀和的积性函数g(x)和h(x), 使得(f*g)(x)=h(x), \\
设h(x)的前缀和为s_h(x), 则有 \\
s_f(x)=\frac{s_h(x)-\sum_{d=2}^ns_f({\left\lfloor\frac nd\right\rfloor})g(d)}{g(1)}
\]

所以我们的任务又变成了找到合适的\(g(x)\)和\(h(x)\).

在某篇歪果仁的blog上, 他说:

With a little luck, we can notice that Id(l) = g * Id2(l),

  • 注: \(id(x)=x\)(以下称为\(n\))\(id2(x)=x^2\)(以下称为\(n_2\))

But 这运气也太好了点吧? 我怎么就找不到这种函数呢?!

不过我们还是要考虑一下的... (这波化式子的时候注意乘号\(\cdot\)和卷积号\(*\))

\[g(x)=\sum_{d|x}\mu(d)xd \\
=\sum_{d|x}d^2\mu(d)\frac xd \\
=(n^2\cdot\mu*n)(x) \\
(g*n_2)(x) \\
=((n^2\cdot\mu*n)*n_2)(x) \cdots ① \\
积性函数有一个性质, 如果两边的乘积都含有某一项的时候, 可以把这一项提出来. \\
所以我们可以把x^2都提出来, (证明可以用定义式推咯~) \\
①=((n^2\cdot\mu*n_2)*n)(x) \\
=(n^2\cdot(\mu*1)*n)(x) \\
=(n^2\cdot\epsilon*n)(x) =n(x)
\]

所以我们就证明出来了\((g*n_2)(x)=n(x)\)

这样就可以直接杜教筛了= =

然后就是注意细节了OvO

比如非常坑人的\(10^{10}*(1e9+7)\)会爆long long!!

所以要开unsigned...

就这样吧= =

代码:

#include <map>
#include <cstring>
#include <iostream>
using namespace std;
typedef unsigned long long LL;
#define ri register int
#define rll register unsigned long long
const int p=1e9+7;
int qpow(int a,int b,int s=1){
for(;b;b>>=1,a=1LL*a*a%p)
if(b&1) s=1LL*s*a%p;
return s;
}
const int inv2=qpow(2,p-2),inv4=qpow(4,p-2),inv6=qpow(6,p-2);
const int N=4800000,_N=N+10;
const int SQ=233333;
LL n;
map<LL,int> mp;
map<LL,int>::iterator it;
int g[_N],pr[N/2],tot;
bool notp[_N];
void shai(){
g[1]=1; ri i,j; rll k;
for(i=2;i<=N;++i){
if(!notp[i])
pr[++tot]=i,g[i]=(-1LL*i*(i-1)%p+p)%p;
for(j=1;j<=tot&&(k=1LL*i*pr[j])<=N;++j){
notp[k]=1;
if(i%pr[j]==0){g[k]=1LL*g[i]*pr[j]%p;break;}
g[k]=1LL*g[i]*g[pr[j]]%p;
}
}
for(i=2;i<=N;++i) g[i]=(g[i]+g[i-1])%p;
}
inline int calcsqr(LL x){x%=p;return x*(x+1)%p*(2*x+1)%p*inv6%p;}
inline int calcsum(LL x){x%=p;return x*x%p*(x+1)%p*(x+1)%p*inv4%p;}
int calc(LL x){
if(x<=N) return g[x];
it=mp.find(x);
if(it!=mp.end()) return it->second;
int ans=1LL*x%p*(x+1)%p*inv2%p;
LL last=0;
for(rll i=2;i<=x;i=last+1){
last=x/(x/i);
ans=(ans-1LL*calc(x/i)*(calcsqr(last)-calcsqr(i-1)+p)%p+p)%p;
}
return mp[x]=(ans%p+p)%p;
}
int main(){
shai();cin>>n;
LL last=0; int ans=0;
for(rll i=1;i<=n;i=last+1){
last=n/(n/i);
ans=(ans+1LL*calcsum(n/i)*(calc(last)-calc(i-1)+p)%p)%p;
}
cout<<ans;
}

这破题我连推带写加总结写了整整一天!!!

窝还是太弱了..

【学术篇】51nod 1238 最小公倍数之和的更多相关文章

  1. 51nod 1238 最小公倍数之和 V3

    51nod 1238 最小公倍数之和 V3 求 \[ \sum_{i=1}^N\sum_{j=1}^N lcm(i,j) \] \(N\leq 10^{10}\) 先按照套路推一波反演的式子: \[ ...

  2. 51NOD 1238 最小公倍数之和 V3 &lbrack;杜教筛&rsqb;

    1238 最小公倍数之和 V3 三种做法!!! 见学习笔记,这里只贴代码 #include <iostream> #include <cstdio> #include < ...

  3. 51nod 1238 最小公倍数之和 V3 【欧拉函数&plus;杜教筛】

    首先题目中给出的代码打错了,少了个等于号,应该是 G=0; for(i=1;i<=N;i++) for(j=1;j<=N;j++) { G = (G + lcm(i,j)) % 10000 ...

  4. &lbrack;51Nod 1238&rsqb; 最小公倍数之和 &lpar;恶心杜教筛&rpar;

    题目描述 求∑i=1N∑j=1Nlcm(i,j)\sum_{i=1}^N\sum_{j=1}^Nlcm(i,j)i=1∑N​j=1∑N​lcm(i,j) 2<=N<=10102<=N ...

  5. 51Nod 1238 最小公倍数之和V3

    题目传送门 分析: 现在我们需要求: \(~~~~\sum_{i=1}^{n}\sum_{j=1}^{n}lcm(i,j)\) \(=\sum_{i=1}^{n}\sum_{j=1}^{n}\frac ...

  6. 51Nod 1238 - 最小公倍数之和 V3(毒瘤数学&plus;杜教筛)

    题目 戳这里 推导 ∑i=1n∑j=1nlcm(i,j)~~~\sum_{i=1}^{n}\sum_{j=1}^{n}lcm(i,j)   ∑i=1n​∑j=1n​lcm(i,j) =∑i=1n∑j= ...

  7. 51nod 1190 最小公倍数之和 V2

    给出2个数a, b,求LCM(a,b) + LCM(a+1,b) + .. + LCM(b,b). 例如:a = 1, b = 6,1,2,3,4,5,6 同6的最小公倍数分别为6,6,6,12,30 ...

  8. 51nod 1363 最小公倍数之和 ——欧拉函数

    给出一个n,求1-n这n个数,同n的最小公倍数的和.例如:n = 6,1,2,3,4,5,6 同6的最小公倍数分别为6,6,6,12,30,6,加在一起 = 66. 由于结果很大,输出Mod 1000 ...

  9. 【51nod】1238 最小公倍数之和 V3 杜教筛

    [题意]给定n,求Σi=1~nΣj=1~n lcm(i,j),n<=10^10. [算法]杜教筛 [题解]就因为写了这个非常规写法,我折腾了3天…… $$ans=\sum_{i=1}^{n}\s ...

随机推荐

  1. Hadoop JAVA 开发说明

    作为Hadoop程序员,他要做的事情就是: 1.定义Mapper,处理输入的Key-Value对,输出中间结果.2.定义Reducer,可选,对中间结果进行规约,输出最终结果.3.定义InputFor ...

  2. 将自己库添加Cocoapods支持

    给库添加Cocoapods支持, 使这个工具使用起来更加方便, 更好的使用Cocoapods, 助力iOS程序开发, 下面进入正题, 想要实现这个过程, 绝对不虚此读. 首先写好一个要添加Cocoap ...

  3. 【iScroll源码学习04】分离IScroll核心

    前言 最近几天我们前前后后基本将iScroll源码学的七七八八了,文章中未涉及的各位就要自己去看了 1. [iScroll源码学习03]iScroll事件机制与滚动条的实现 2. [iScroll源码 ...

  4. RESTful API的重磅好伙伴Swagger2

    本文将介绍RESTful API的重磅好伙伴Swagger2,它可以轻松的整合到Spring Boot中,并与Spring MVC程序配合组织出强大RESTful API文档. 它既可以减少我们创建文 ...

  5. Common Scenarios to avoid with DataWarehousing

    Database Design Rule Description Value Source Problem Description 1 Excessive sorting and RID lookup ...

  6. Dynamic CRM 2013学习笔记(二十一)自定义审批流2 - 配置按钮

    上次介绍了 Dynamic CRM 2013学习笔记(十九)自定义审批流1 - 效果演示 现在开始介绍如何配置审批流,首先在form上添加三个按钮,Submit, Agree, Reject: 1. ...

  7. iOS10新特性之CallKit开发详解:锁屏接听和来电识别

    国庆节过完了,回家好好休息一天,今天好好分享一下CallKit开发.最近发现好多吃瓜问CallKit的VoIP开发适配,对iOS10的新特性开发和适配也在上个月完成,接下来就分享一下VoIP应用如何使 ...

  8. 解决服务器连接错误Host &OpenCurlyQuote;XXX’ is not allowed to connect to this MySQL server

    这段时间在研究火车头的入库教程,在“配置登陆信息和数据库(mysql)”连接中,出现“服务器连接错误Host 'XXX' is not allowed to connect to this MySQL ...

  9. html textarea换行和dom换行

    从事开发已经两年多了,但是还是不会发现问题找原因,可能是自己一直在学校养成的习惯吧,不过最近在葛经理的带领下开始学会找原因了,而且发现自己变得更成熟了. 现在讲讲textarea和dom的换行吧,我们 ...

  10. 第二个C语言代码

    有问题,还没找出哪里出错了       输入一串字符,问号结束 统计1~9各出现的次数 ******************************************************** ...