#莫比乌斯反演,整除分块#bzoj 2154 bzoj 2693 jzoj 1938 洛谷 1829 Crash的数字表格 or JZPTAB

本文主要是介绍#莫比乌斯反演,整除分块#bzoj 2154 bzoj 2693 jzoj 1938 洛谷 1829 Crash的数字表格 or JZPTAB,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目

∑ i = 1 n ∑ j = 1 m l c m ( i , j ) \sum_{i=1}^n\sum_{j=1}^mlcm(i,j) i=1nj=1mlcm(i,j)


分析

原式= ∑ i = 1 n ∑ j = 1 m i j g c d ( i , j ) \sum_{i=1}^n\sum_{j=1}^m\frac{ij}{gcd(i,j)} i=1nj=1mgcd(i,j)ij
那么原式= ∑ d = 1 m i n ( n , m ) d × ∑ i = 1 ⌊ n d ⌋ ∑ j = 1 ⌊ m d ⌋ [ g c d ( i , j ) = 1 ] × i × j \sum_{d=1}^{min(n,m)}d\times \sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}[gcd(i,j)=1]\times i\times j d=1min(n,m)d×i=1dnj=1dm[gcd(i,j)=1]×i×j
根据莫比乌斯反演可以得到原式= ∑ d = 1 m i n ( n , m ) d ∑ t = 1 m i n ( ⌊ n d ⌋ , ⌊ m d ⌋ ) t 2 μ ( t ) ∑ i = 1 ⌊ n d t ⌋ i ∑ j = 1 ⌊ m d t ⌋ j \sum_{d=1}^{min(n,m)}d\sum_{t=1}^{min(\lfloor\frac{n}{d}\rfloor,\lfloor\frac{m}{d}\rfloor)}t^2\mu(t)\sum_{i=1}^{\lfloor\frac{n}{dt}\rfloor}i\sum_{j=1}^{\lfloor\frac{m}{dt}\rfloor}j d=1min(n,m)dt=1min(dn,dm)t2μ(t)i=1dtnij=1dtmj
就可以预处理 t 2 μ ( t ) t^2\mu(t) t2μ(t),用整除分块求解,时间复杂度大概是 O ( n ) O(n) O(n)


代码

#include <cstdio>
#define rr register
#define min(a,b) ((a)<(b)?(a):(b))
#define res(n,m) ((1ll*n*(n+1)>>1)%mod*((1ll*m*(m+1)>>1)%mod)%mod)
using namespace std;
const int mod=20101009,M=10000010;
int n,m,v[M],prime[M],s[M],cnt;
inline void prepa(int N){s[1]=1;for (rr int i=2;i<=N;++i){if (!v[i]) s[i]=-1,v[i]=prime[++cnt]=i;for (rr int j=1;j<=cnt&&prime[j]*i<=N;++j){v[i*prime[j]]=prime[j];if (i%prime[j]) s[i*prime[j]]=-s[i];else break;}}for (rr int i=1;i<=N;++i) s[i]=1ll*i*i%mod*(s[i]+mod)%mod;for (rr int i=2;i<=N;++i) (s[i]+=s[i-1])%=mod;
}
inline signed answ(int n,int m){rr int ans=0,t=min(n,m);for (rr int l=1,r;l<=t;l=r+1){r=min(n/(n/l),m/(m/l));(ans+=1ll*(s[r]-s[l-1]+mod)*res(n/l,m/l)%mod)%=mod;}return ans;
}
inline signed solve(int n,int m){rr int ans=0,t;prepa(t=min(n,m)); for (rr int l=1,r;l<=t;l=r+1){r=min(n/(n/l),m/(m/l));(ans+=(1ll*(r-l+1)*(l+r)>>1)%mod*answ(n/l,m/l)%mod)%=mod;}return ans;
}
signed main(){scanf("%d%d",&n,&m);printf("%d",solve(n,m));return 0;
} 

这篇关于#莫比乌斯反演,整除分块#bzoj 2154 bzoj 2693 jzoj 1938 洛谷 1829 Crash的数字表格 or JZPTAB的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/698981

相关文章

HTML5表格语法格式详解

《HTML5表格语法格式详解》在HTML语法中,表格主要通过table、tr和td3个标签构成,本文通过实例代码讲解HTML5表格语法格式,感兴趣的朋友一起看看吧... 目录一、表格1.表格语法格式2.表格属性 3.例子二、不规则表格1.跨行2.跨列3.例子一、表格在html语法中,表格主要通过< tab

Python实现特殊字符判断并去掉非字母和数字的特殊字符

《Python实现特殊字符判断并去掉非字母和数字的特殊字符》在Python中,可以通过多种方法来判断字符串中是否包含非字母、数字的特殊字符,并将这些特殊字符去掉,本文为大家整理了一些常用的,希望对大家... 目录1. 使用正则表达式判断字符串中是否包含特殊字符去掉字符串中的特殊字符2. 使用 str.isa

C#实现将Excel表格转换为图片(JPG/ PNG)

《C#实现将Excel表格转换为图片(JPG/PNG)》Excel表格可能会因为不同设备或字体缺失等问题,导致格式错乱或数据显示异常,转换为图片后,能确保数据的排版等保持一致,下面我们看看如何使用C... 目录通过C# 转换Excel工作表到图片通过C# 转换指定单元格区域到图片知识扩展C# 将 Excel

利用Python开发Markdown表格结构转换为Excel工具

《利用Python开发Markdown表格结构转换为Excel工具》在数据管理和文档编写过程中,我们经常使用Markdown来记录表格数据,但它没有Excel使用方便,所以本文将使用Python编写一... 目录1.完整代码2. 项目概述3. 代码解析3.1 依赖库3.2 GUI 设计3.3 解析 Mark

使用PyTorch实现手写数字识别功能

《使用PyTorch实现手写数字识别功能》在人工智能的世界里,计算机视觉是最具魅力的领域之一,通过PyTorch这一强大的深度学习框架,我们将在经典的MNIST数据集上,见证一个神经网络从零开始学会识... 目录当计算机学会“看”数字搭建开发环境MNIST数据集解析1. 认识手写数字数据库2. 数据预处理的

java字符串数字补齐位数详解

《java字符串数字补齐位数详解》:本文主要介绍java字符串数字补齐位数,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java字符串数字补齐位数一、使用String.format()方法二、Apache Commons Lang库方法三、Java 11+的St

Java利用poi实现word表格转excel

《Java利用poi实现word表格转excel》这篇文章主要为大家详细介绍了Java如何利用poi实现word表格转excel,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 一、每行对象类需要针对不同的表格进行对应的创建。package org.example.wordToEx

python中的整除向下取整的操作方法

《python中的整除向下取整的操作方法》Python中的//是整数除法运算符,用于执行向下取整的除法,返回商的整数部分,不会四舍五入,它在分治法、索引计算和整数运算中非常有用,本文给大家介绍pyth... 目录1. // 的基本用法2. // vs /(普通除法)3. // 在 mid = len(lis

使用EasyExcel实现简单的Excel表格解析操作

《使用EasyExcel实现简单的Excel表格解析操作》:本文主要介绍如何使用EasyExcel完成简单的表格解析操作,同时实现了大量数据情况下数据的分次批量入库,并记录每条数据入库的状态,感兴... 目录前言固定模板及表数据格式的解析实现Excel模板内容对应的实体类实现AnalysisEventLis

使用Python实现表格字段智能去重

《使用Python实现表格字段智能去重》在数据分析和处理过程中,数据清洗是一个至关重要的步骤,其中字段去重是一个常见且关键的任务,下面我们看看如何使用Python进行表格字段智能去重吧... 目录一、引言二、数据重复问题的常见场景与影响三、python在数据清洗中的优势四、基于Python的表格字段智能去重