BZOJ 2005 [Noi2010]能量采集 (容斥)

2024-03-20 13:58

本文主要是介绍BZOJ 2005 [Noi2010]能量采集 (容斥),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

 [Noi2010]能量采集

Time Limit: 10 Sec  Memory Limit: 552 MB
Submit: 2324  Solved: 1387
[Submit][Status][Discuss]

Description

栋栋有一块长方形的地,他在地上种了一种能量植物,这种植物可以采集太阳光的能量。在这些植物采集能量后,栋栋再使用一个能量汇集机器把这些植物采集到的能量汇集到一起。 栋栋的植物种得非常整齐,一共有n列,每列有m棵,植物的横竖间距都一样,因此对于每一棵植物,栋栋可以用一个坐标(x, y)来表示,其中x的范围是1至n,表示是在第x列,y的范围是1至m,表示是在第x列的第y棵。 由于能量汇集机器较大,不便移动,栋栋将它放在了一个角上,坐标正好是(0, 0)。 能量汇集机器在汇集的过程中有一定的能量损失。如果一棵植物与能量汇集机器连接而成的线段上有k棵植物,则能量的损失为2k + 1。例如,当能量汇集机器收集坐标为(2, 4)的植物时,由于连接线段上存在一棵植物(1, 2),会产生3的能量损失。注意,如果一棵植物与能量汇集机器连接的线段上没有植物,则能量损失为1。现在要计算总的能量损失。 下面给出了一个能量采集的例子,其中n = 5,m = 4,一共有20棵植物,在每棵植物上标明了能量汇集机器收集它的能量时产生的能量损失。 在这个例子中,总共产生了36的能量损失。

Input

仅包含一行,为两个整数n和m。

Output

仅包含一个整数,表示总共产生的能量损失。

Sample Input

【样例输入1】
5 4

【样例输入2】
3 4

Sample Output

【样例输出1】
36

【样例输出2】
20

【数据规模和约定】
对于10%的数据:1 ≤ n, m ≤ 10;

对于50%的数据:1 ≤ n, m ≤ 100;

对于80%的数据:1 ≤ n, m ≤ 1000;

对于90%的数据:1 ≤ n, m ≤ 10,000;

对于100%的数据:1 ≤ n, m ≤ 100,000。


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=2005


题目分析:首先不难发现点(x,y)和(0,0)点之间的植物个数为gcd(x,y)-1,因此题目要求的实际上就是Σi(1-n)Σj(1-m) [2 * (gcd(i, j) - 1) - 1],化简一下得 2 * Σi(1-n)Σj(1-m) gcd(i, j) - n * m,现在问题就是如何快速求Σi(1-n)Σj(1-m) gcd(i, j),可以用莫比乌斯反演搞,不过直接nlogn的容斥就可以了,cnt[i]记录的是最大公约数为i的二元组个数,首先(n / i) * (m / i)是所有以i为公约数的二元组个数  那么拿cnt[i]减去所有的cnt[j](j为i的倍数),剩下的就是所有以i为最大公约数的二元组个数,注意这里枚举约数时要倒序,因为我们要用小的减大的,要保证大的已经算出来了,然后按照公式计算即可,注意要用long long


#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
int const MAX = 1e5 + 5;
ll cnt[MAX];int main()
{ll ans = 0;memset(cnt, 0, sizeof(cnt));ll n, m;scanf("%lld %lld", &n, &m);if(n < m)swap(n, m);for(int i = n; i >= 1; i--){cnt[i] = (ll) (n / i) * (m / i);for(int j = i * 2; j <= n; j += i)cnt[i] -= cnt[j];ans += i * cnt[i];}printf("%lld\n", 2 * ans - n * m);
}



这篇关于BZOJ 2005 [Noi2010]能量采集 (容斥)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

hdu4407(容斥原理)

题意:给一串数字1,2,......n,两个操作:1、修改第k个数字,2、查询区间[l,r]中与n互质的数之和。 解题思路:咱一看,像线段树,但是如果用线段树做,那么每个区间一定要记录所有的素因子,这样会超内存。然后我就做不来了。后来看了题解,原来是用容斥原理来做的。还记得这道题目吗?求区间[1,r]中与p互质的数的个数,如果不会的话就先去做那题吧。现在这题是求区间[l,r]中与n互质的数的和

hdu4407容斥原理

题意: 有一个元素为 1~n 的数列{An},有2种操作(1000次): 1、求某段区间 [a,b] 中与 p 互质的数的和。 2、将数列中某个位置元素的值改变。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.Inpu

hdu4059容斥原理

求1-n中与n互质的数的4次方之和 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWrit

Verybot之OpenCV应用一:安装与图像采集测试

在Verybot上安装OpenCV是很简单的,只需要执行:         sudo apt-get update         sudo apt-get install libopencv-dev         sudo apt-get install python-opencv         下面就对安装好的OpenCV进行一下测试,编写一个通过USB摄像头采

容斥问题

一、填空题 1.一个班有45个小学生,统计借课外书的情况是:全班学生都借有语文或数学课外书.借语文课外书的有39人,借数学课外书的有32人.语文、数学两种课外书都借的有     人. 3.在1~100的自然数中,是5的倍数或是7的倍数的数有     个. 4.某区100个外语教师懂英语或俄语,其中懂英语的75人,既懂英语又懂俄语的20人,那么懂俄语的教师为     人. 5.六一班

Python 爬虫入门 - 基础数据采集

Python网络爬虫是一种强大且灵活的工具,用于从互联网上自动化地获取和处理数据。无论你是数据科学家、市场分析师,还是一个想要深入了解互联网数据的开发者,掌握网络爬虫技术都将为你打开一扇通向丰富数据资源的大门。 在本教程中,我们将从基本概念入手,逐步深入了解如何构建和优化网络爬虫,涵盖从发送请求、解析网页结构到保存数据的全过程,并讨论如何应对常见的反爬虫机制。通过本教程,你将能够构建有效的网络爬

能量项链,洛谷

解释:  环形dp问题还是考虑将环拉直,可以参考我上一篇文章:环形石子合并 [2 3 5 10 2] 3 5 10 将环拉直,[]内是一个有效的区间,可以模拟吸收珠子的过程,         如[2 3 5] <=>(2,3)(3,5)    2是头,3是中间,5是尾 len >= 3:因为最后[2 10 2]是最小的可以合并的有效区间 len <= n + 1因为[2 3

Python 爬虫入门 - 基础数据采集流程拓展

在网络爬虫的世界里,数据就是一切。通过爬虫技术,你可以自动化地收集各种类型的公开数据,从文本和图片到复杂的结构化信息,这些数据为各类分析和应用提供了基础。 本教程将引导你深入了解爬虫可以采集的数据种类,如何有效地获取这些数据,并探讨如何使用代理服务来规避限制与增强爬虫的灵活性。无论是初学者还是有经验的开发者,这些知识都将帮助你在网络数据采集中更加游刃有余。 文章目录 可采集的数据基本操作

景联文科技:专业图像采集服务,助力智能图像分析

景联文科技是专业数据服务公司,致力于为人工智能企业提供从数据采集、清洗到标注的全流程解决方案。协助客户解决AI开发过程中数据处理环节的关键问题,助力企业实现智能化转型。 1.多样化的图像采集服务 景联文科技提供多样化的图像采集服务,涵盖不同应用场景和需求: •高分辨率图像采集:适用于高质量图像需求,如医学影像、工业检测等。 •实时图像采集:适用于需要实时处理的应用场景,如安防监

大隈设备采集

大隈(OKUMA)荣一在名古屋东区成立自己的私人公司,开始制造、销售制面机械。下面是社长的一些介绍:我司自1898年生产·销售制面机开始创业以来,秉承若所需之物世间尚无,必不妥协,独自创造的“破土创新”精神,并将其一脉相承,于1904年开始进行机床的生产。自创业以来,历经120余年,从未间断对先进技术和产品的开发。1963年,作为日本机床制造商,首次自主研发出数控装置“OSP”,利