51 NOD 1238 最小公倍数之和 V3

时间:2022-08-31 23:58:57

原题链接

最近被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的更多相关文章

  1. 51 Nod 1238 最小公倍数之和 V3 杜教筛

    题目链接:http://www.51nod.com/Challenge/Problem.html#!#problemId=1238 题意:求$\sum_{i=1}^{n}\sum_{j=1}^{n}l ...

  2. 51NOD 1238 最小公倍数之和 V3 [杜教筛]

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

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

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

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

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

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

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

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

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

  7. 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= ...

  8. 51 nod 1023 石子归并 V3&lpar;GarsiaWachs算法&rpar;

    1023 石子归并 V3基准时间限制:2 秒 空间限制:131072 KB 分值: 320 难度:7级算法题 N堆石子摆成一条线.现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆石子合并成新的一 ...

  9. 51 Nod 1110距离之和最小V3

    1110 距离之和最小 V3 1 秒 131,072 KB 40 分 4 级题 X轴上有N个点,每个点除了包括一个位置数据X[i],还包括一个权值W[i].点P到点P[i]的带权距离 = 实际距离 * ...

随机推荐

  1. 老猪带你玩转android自定义控件一——打造最简单viewpagerindicator

    viewpagerindicator,既使用viewpager翻页时候,标题的指示条随着改变的控件,是常用android控件之一,几乎所有的新闻类APP中都有使用.如下图所示: 今天,我们将从0到1实 ...

  2. ACM 杂题&comma;思路题 整理

    UVa 11572 - Unique Snowflakes 问一个数组中,无重复数字的最长子串长度是多少. 用map维护某数字上次出现的位置.另外用变量last表示上次出现数字重复的位置. 如果出现重 ...

  3. css的6中居中的方式

    请先看blog:http://blog.csdn.net/wolinxuebin/article/details/7615098

  4. Codeforces Gym 100733J Summer Wars 线段树,区间更新,区间求最大值,离散化,区间求并

    Summer WarsTime Limit: 20 Sec Memory Limit: 256 MB 题目连接 http://acm.hust.edu.cn/vjudge/contest/view.a ...

  5. Android 源码VecotorDrawable

    1 R.styleable.VectorDrawable_viewportWidth 该资源的名字并非VectorDrawable_viewportWidth 而是 attrs.xml 下的声明 &l ...

  6. php中带mb的字符串处理函数

    int strlen ( string $string ) int mb_strlen ( string $str [, string $encoding ] ) encoding参数为字符编码.如果 ...

  7. Bitmap的一个简单实现

    一.Bitmap简介 Bitmap是一种常用的数据结构,其实就是一个连续的数组,主要是用于映射关系,如映射整数,一位代表一个数,即这里假设Bitmap有100Bytes * 8 这么多的位,那么这里可 ...

  8. hihocoder 1419 重复旋律4

    描述 小Hi平时的一大兴趣爱好就是演奏钢琴.我们知道一个音乐旋律被表示为长度为 N 的数构成的数列.小Hi在练习过很多曲子以后发现很多作品中的旋律有重复的部分. 我们把一段旋律称为(k,l)-重复的, ...

  9. C&plus;&plus;基础——类继承

    一.前言  好吧,本系列博客已经变成了<C++ Primer Plus>的读书笔记,尴尬.在使用C语言时,多通过添加库函数的方式实现代码重用,但有一个弊端就是原来写好的代码并不完全适用于现 ...

  10. OpenCV4&period;1&period;0实践&lpar;1&rpar; - 环境配置及使用

    Pycharm下虚拟环境配置 1.下载whl文件 下载地址:python extension packages 搜索opencv,根据自己的版本下载,我用的python版本是3.5.2,64位: 2. ...