最近被51NOD的数论题各种刷……(NOI快到了我在干什么啊!
然后发现这题在网上找不到题解……那么既然A了就来骗一波访问量吧……
(然而并不怎么会用什么公式编辑器,写得丑也凑合着看吧……
$$
ANS=\sum_{i=1}^{n}\sum_{j=1}^{n} \frac{i*j}{gcd(i,j)}
$$
$$
=\sum_{d=1}^{n} d*\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor} \sum_{j=1}^{\left\lfloor\frac{n}{d}\right\rfloor} i*j*[gcd(i,j)==1]
$$
$$
=\sum_{d=1}^{n} d*\sum_{d'=1}^{\left\lfloor\frac{n}{d}\right\rfloor} f(\left\lfloor\frac{n}{d*d'}\right\rfloor)*d'^2*μ(d')
$$
$$
=\sum_{d'=1}^{n} d'^2*μ(d')*\sum_{d=1}^{\left\lfloor\frac{n}{d'}\right\rfloor} d*f(\left\lfloor\frac{n}{d*d'}\right\rfloor)
$$
这里$f(x)=(\frac{x*(x+1)}{2})^2$,即1到x中数字之间两两乘积之和。
可以看出不同的$\left\lfloor\frac{n}{d'}\right\rfloor$只有根号n个,对于某一个$\left\lfloor\frac{n}{d'}\right\rfloor$,不同的$\left\lfloor\frac{n}{d*d'}\right\rfloor$也只有根号n个,那么把它们压在一起处理就好了。
但是要做到这一点需要快速求出$d'^2*μ(d')$的前缀和,这时就要用上杜教筛了。
记$g(x)=x^2*μ(x)$,$S(x)=\sum_{i=1}^{x} g(i)$
那么
$ \sum_{i=1}^{n} \sum_{x|i} g(x)*(\frac{i}{x})^2$
$=\sum_{i=1}^{n} i*\sum_{x|i} μ(x)$
$=\sum_{i=1}^{n} [i==1] $
$= 1$
同时
$ \sum_{i=1}^{n} \sum_{x|i} g(x)*(\frac{i}{x})^2$
$=\sum_{i=1}^{n} \sum_{x=1}^{[\frac{n}{i}]} g(x)*i^2$
$=\sum_{i=1}^{n} i^2*S[\frac{n}{i}]$
可以得到$S(n)=1-\sum_{i=2}^{n} i^2*S[\frac{n}{i}]$,预处理+哈希维护一波就行了
但是不知道是我常数太大,还是方法没别人优越,卡了很久常数才卡过去。
代码自己码啦!
51 NOD 1238 最小公倍数之和 V3的更多相关文章
-
51 Nod 1238 最小公倍数之和 V3 杜教筛
题目链接:http://www.51nod.com/Challenge/Problem.html#!#problemId=1238 题意:求$\sum_{i=1}^{n}\sum_{j=1}^{n}l ...
-
51NOD 1238 最小公倍数之和 V3 [杜教筛]
1238 最小公倍数之和 V3 三种做法!!! 见学习笔记,这里只贴代码 #include <iostream> #include <cstdio> #include < ...
-
51nod 1238 最小公倍数之和 V3
51nod 1238 最小公倍数之和 V3 求 \[ \sum_{i=1}^N\sum_{j=1}^N lcm(i,j) \] \(N\leq 10^{10}\) 先按照套路推一波反演的式子: \[ ...
-
【51nod】1238 最小公倍数之和 V3 杜教筛
[题意]给定n,求Σi=1~nΣj=1~n lcm(i,j),n<=10^10. [算法]杜教筛 [题解]就因为写了这个非常规写法,我折腾了3天…… $$ans=\sum_{i=1}^{n}\s ...
-
51nod 1238 最小公倍数之和 V3 【欧拉函数+杜教筛】
首先题目中给出的代码打错了,少了个等于号,应该是 G=0; for(i=1;i<=N;i++) for(j=1;j<=N;j++) { G = (G + lcm(i,j)) % 10000 ...
-
51Nod 1238 最小公倍数之和V3
题目传送门 分析: 现在我们需要求: \(~~~~\sum_{i=1}^{n}\sum_{j=1}^{n}lcm(i,j)\) \(=\sum_{i=1}^{n}\sum_{j=1}^{n}\frac ...
-
51Nod 1238 - 最小公倍数之和 V3(毒瘤数学+杜教筛)
题目 戳这里 推导 ∑i=1n∑j=1nlcm(i,j)~~~\sum_{i=1}^{n}\sum_{j=1}^{n}lcm(i,j) ∑i=1n∑j=1nlcm(i,j) =∑i=1n∑j= ...
-
51 nod 1023 石子归并 V3(GarsiaWachs算法)
1023 石子归并 V3基准时间限制:2 秒 空间限制:131072 KB 分值: 320 难度:7级算法题 N堆石子摆成一条线.现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆石子合并成新的一 ...
-
51 Nod 1110距离之和最小V3
1110 距离之和最小 V3 1 秒 131,072 KB 40 分 4 级题 X轴上有N个点,每个点除了包括一个位置数据X[i],还包括一个权值W[i].点P到点P[i]的带权距离 = 实际距离 * ...
随机推荐
-
老猪带你玩转android自定义控件一——打造最简单viewpagerindicator
viewpagerindicator,既使用viewpager翻页时候,标题的指示条随着改变的控件,是常用android控件之一,几乎所有的新闻类APP中都有使用.如下图所示: 今天,我们将从0到1实 ...
-
ACM 杂题,思路题 整理
UVa 11572 - Unique Snowflakes 问一个数组中,无重复数字的最长子串长度是多少. 用map维护某数字上次出现的位置.另外用变量last表示上次出现数字重复的位置. 如果出现重 ...
-
css的6中居中的方式
请先看blog:http://blog.csdn.net/wolinxuebin/article/details/7615098
-
Codeforces Gym 100733J Summer Wars 线段树,区间更新,区间求最大值,离散化,区间求并
Summer WarsTime Limit: 20 Sec Memory Limit: 256 MB 题目连接 http://acm.hust.edu.cn/vjudge/contest/view.a ...
-
Android 源码VecotorDrawable
1 R.styleable.VectorDrawable_viewportWidth 该资源的名字并非VectorDrawable_viewportWidth 而是 attrs.xml 下的声明 &l ...
-
php中带mb的字符串处理函数
int strlen ( string $string ) int mb_strlen ( string $str [, string $encoding ] ) encoding参数为字符编码.如果 ...
-
Bitmap的一个简单实现
一.Bitmap简介 Bitmap是一种常用的数据结构,其实就是一个连续的数组,主要是用于映射关系,如映射整数,一位代表一个数,即这里假设Bitmap有100Bytes * 8 这么多的位,那么这里可 ...
-
hihocoder 1419 重复旋律4
描述 小Hi平时的一大兴趣爱好就是演奏钢琴.我们知道一个音乐旋律被表示为长度为 N 的数构成的数列.小Hi在练习过很多曲子以后发现很多作品中的旋律有重复的部分. 我们把一段旋律称为(k,l)-重复的, ...
-
C++基础——类继承
一.前言 好吧,本系列博客已经变成了<C++ Primer Plus>的读书笔记,尴尬.在使用C语言时,多通过添加库函数的方式实现代码重用,但有一个弊端就是原来写好的代码并不完全适用于现 ...
-
OpenCV4.1.0实践(1) - 环境配置及使用
Pycharm下虚拟环境配置 1.下载whl文件 下载地址:python extension packages 搜索opencv,根据自己的版本下载,我用的python版本是3.5.2,64位: 2. ...