洛谷P1829 - [国家集训队]Crash的数字表格

2024-03-19 17:58

本文主要是介绍洛谷P1829 - [国家集训队]Crash的数字表格,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Portal

Description

给出\(n,m(n,m\leq10^7)\),计算\[ \sum_{i=1}^n \sum_{j=1}^m lcm(i,j) \bmod 20101009\]
fdsa

Solution

推推推...
\[\begin{align} ans &= \sum_{i=1}^n \sum_{j=1}^m lcm(i,j) \\ &= \sum_{i=1}^n \sum_{j=1}^m \frac{ij}{gcd(i,j)} \\ &= \sum_{d=1}^n \sum_{i=1}^n \sum_{j=1}^m \frac{ij}{d}[gcd(i,j)=d] \\ &= \sum_{d=1}^n \sum_{i=1}^{⌊\frac{n}{d}⌋} \sum_{j=1}^{⌊\frac{m}{d}⌋} ijd[gcd(i,j)=1] \\ &= \sum_{d=1}^n \sum_{i=1}^{⌊\frac{n}{d}⌋} \sum_{j=1}^{⌊\frac{m}{d}⌋} ijd \sum_{d'|gcd(i,j)} \mu(d') \\ &= \sum_{d=1}^n \sum_{d'=1}^n d\mu(d') \sum_{d'|i}^{⌊\frac{n}{d}⌋} \sum_{d'|j}^{⌊\frac{m}{d}⌋} ij \\ &= \sum_{d=1}^n \sum_{d'=1}^n d\mu(d') \sum_{i=1}^{⌊\frac{n}{dd'}⌋} \sum_{j=1}^{⌊\frac{m}{dd'}⌋} ijd'^2 \\ &= \frac{1}{4} \sum_{d=1}^n \sum_{d'=1}^n dd'^2\mu(d') (1+⌊\frac{n}{dd'}⌋)⌊\frac{n}{dd'}⌋(1+⌊\frac{m}{dd'}⌋)⌊\frac{m}{dd'}⌋ \\ &= \frac{1}{4} \sum_{d=1}^n (1+⌊\frac{n}{d}⌋)⌊\frac{n}{d}⌋(1+⌊\frac{m}{d}⌋)⌊\frac{m}{d}⌋ \sum_{d'|d} dd'\mu(d') \end{align}\] \((8)\)\((9)\)转换了枚举对象,\(d=dd',d'=d'\)
前面的部分可以\(O(\sqrt n)\)搞定,那么我们只需要考虑求出\(g(d)=\sum_{d'|d} dd'\mu(d')\)的前缀和。由于积性函数的积是积性函数,积性函数的卷积也是积性函数,所以\(g(d)\)是积性函数,可以在\(O(n)\)的时间内预处理出来。

时间复杂度\(O(n)\)

Code

//[国家集训队]Crash的数字表格
#include <algorithm>
#include <cstdio>
using std::min; using std::swap;
typedef long long lint;
const int N=1e7+10;
const int H=20101009;
int mu[N]; lint f[N];
int cntP,pr[N],p1[N]; bool notP[N];
void init(int n)
{mu[1]=1,f[1]=1;for(lint i=2;i<=n;i++){if(!notP[i]){pr[++cntP]=i; p1[i]=i;mu[i]=-1,f[i]=(1-i+H)*i%H;for(lint j=i*i;j<=n;j*=i) p1[j]=j,mu[j]=0,f[j]=(1-i+H)*j%H;}for(int j=1;j<=cntP;j++){lint x=pr[j]*i; if(x>n) break;notP[x]=true;if(i%pr[j]) p1[x]=pr[j],mu[x]=-mu[i],f[x]=f[pr[j]]*f[i]%H;else {p1[x]=p1[i]*pr[j],mu[x]=0,f[x]=f[p1[x]]*f[x/p1[x]]%H; break;}}}for(int i=1;i<=n;i++) f[i]+=f[i-1];
}
int main()
{int n,m; scanf("%d%d",&n,&m);if(n>m) swap(n,m); init(n);lint ans=0;for(int L=1,R;L<=n;L=R+1){lint v1=n/L,v2=m/L; R=min(n/v1,m/v2);ans+=(1+v1)*v1%H*(1+v2)%H*v2%H*(f[R]-f[L-1]+H)%H;ans%=H;}printf("%lld\n",ans*15075757%H);    //inv(4)=15075757return 0;
}

P.S.

这似乎只是入门题...

转载于:https://www.cnblogs.com/VisJiao/p/LgP1829.html

这篇关于洛谷P1829 - [国家集训队]Crash的数字表格的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

利用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

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

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

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

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

Java数字转换工具类NumberUtil的使用

《Java数字转换工具类NumberUtil的使用》NumberUtil是一个功能强大的Java工具类,用于处理数字的各种操作,包括数值运算、格式化、随机数生成和数值判断,下面就来介绍一下Number... 目录一、NumberUtil类概述二、主要功能介绍1. 数值运算2. 格式化3. 数值判断4. 随机

如何利用Python实现给Excel表格截图

《如何利用Python实现给Excel表格截图》这篇文章主要为大家详细介绍了如何利用Python实现给Excel表格截图功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 我搜索了网络上的方案,感觉把 Excel 表格转换为 html 再用 platwright 截图是比China编程较顺

vue基于ElementUI动态设置表格高度的3种方法

《vue基于ElementUI动态设置表格高度的3种方法》ElementUI+vue动态设置表格高度的几种方法,抛砖引玉,还有其它方法动态设置表格高度,大家可以开动脑筋... 方法一、css + js的形式这个方法需要在表格外层设置一个div,原理是将表格的高度设置成外层div的高度,所以外层的div需要

使用SQL语言查询多个Excel表格的操作方法

《使用SQL语言查询多个Excel表格的操作方法》本文介绍了如何使用SQL语言查询多个Excel表格,通过将所有Excel表格放入一个.xlsx文件中,并使用pandas和pandasql库进行读取和... 目录如何用SQL语言查询多个Excel表格如何使用sql查询excel内容1. 简介2. 实现思路3