HDU 2841:Visible Trees ← 容斥原理

2024-01-07 05:52

本文主要是介绍HDU 2841:Visible Trees ← 容斥原理,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

【题目来源】
http://acm.hdu.edu.cn/showproblem.php?pid=2841

【题目描述】
There are many trees forming a m * n grid, the grid starts
from (1,1). Farmer Sherlock is standing at (0,0) point. He wonders how many trees he can see.
If two trees and Sherlock are in one line, Farmer Sherlock can only see the tree nearest to him.

【输入格式】
The first line contains one integer t, represents the number of test cases. Then there are multiple test cases. For each test case there is one line containing two integers m and n(1 ≤ m, n ≤ 100000)

【输出格式】
For each test case output one line represents the number of trees Farmer Sherlock can see.

【输入样例】
2
1 1
2 3

【输出样例】
1
5

【算法分析】
在计数时,必须注意无一重复,无一遗漏。为了使重叠部分不被重复计算,人们研究出一种计数方法,这种方法的基本思想是:先不考虑重叠的情况,把包含于某内容中的所有对象的数目先计算出来,然后再把计数时重复计算的数目排斥出去,使得计算的结果既无遗漏又无重复,这种计数的方法称为
容斥原理

针对本题,显然,若 (x,y) 能被看到,那么 (k*x, k*y) 都不能被看到(其中,k>1)。
因此,问题转化为求 1<=x<=n 且 1<=y<=m 有多个 <x,y> 满足 gcd(x,y)=1。
那么可以从 1~n 枚举 x,累计 1~m 中与 x 互质的个数。
对 x 分解素因子,容斥一下就可得到结果。

【算法代码】

#include <iostream>
#include <vector>
using namespace std;typedef long long LL;
vector<int> v;
int n,m;void pfac(int x) { //Find all the prime factors of xv.clear();for(int i=2; i*i<=x; i++) {if(x%i==0) {v.push_back(i);while(x%i==0) x/=i;}}if(x>1) v.push_back(x);
}int solve(int x) {int sum=0;for(int i=1; i<(1<<v.size()); i++) {int res=1,cnt=0;for(int j=0; j<v.size(); j++) {if(i & (1<<j)) {res*=v[j];cnt++;}}if(cnt & 1) sum+=x/res;else sum-=x/res;}return sum;
}int main() {int T;cin>>T;while(T--) {scanf("%d %d",&n,&m); //cin>>n>>m;LL ans=m;for(int i=2; i<=n; i++) {pfac(i);ans+=m-solve(m);}printf("%lld\n",ans);}
}/*
in:
2
1 1
2 3out:
1
5
*/




【参考文献】
https://www.cnblogs.com/00isok/p/10358598.html
https://blog.csdn.net/weixin_53746961/article/details/121175561
https://blog.csdn.net/weixin_43846139/article/details/105517437
https://www.cnblogs.com/crackpotisback/p/4846909.html
http://www.manongjc.com/detail/39-wpncookuuhcoyui.html
https://blog.csdn.net/weixin_30710457/article/details/98919034




 

这篇关于HDU 2841:Visible Trees ← 容斥原理的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Spring Boot循环依赖原理、解决方案与最佳实践(全解析)

《SpringBoot循环依赖原理、解决方案与最佳实践(全解析)》循环依赖指两个或多个Bean相互直接或间接引用,形成闭环依赖关系,:本文主要介绍SpringBoot循环依赖原理、解决方案与最... 目录一、循环依赖的本质与危害1.1 什么是循环依赖?1.2 核心危害二、Spring的三级缓存机制2.1 三

C#中async await异步关键字用法和异步的底层原理全解析

《C#中asyncawait异步关键字用法和异步的底层原理全解析》:本文主要介绍C#中asyncawait异步关键字用法和异步的底层原理全解析,本文给大家介绍的非常详细,对大家的学习或工作具有一... 目录C#异步编程一、异步编程基础二、异步方法的工作原理三、代码示例四、编译后的底层实现五、总结C#异步编程

Go 语言中的select语句详解及工作原理

《Go语言中的select语句详解及工作原理》在Go语言中,select语句是用于处理多个通道(channel)操作的一种控制结构,它类似于switch语句,本文给大家介绍Go语言中的select语... 目录Go 语言中的 select 是做什么的基本功能语法工作原理示例示例 1:监听多个通道示例 2:带

鸿蒙中@State的原理使用详解(HarmonyOS 5)

《鸿蒙中@State的原理使用详解(HarmonyOS5)》@State是HarmonyOSArkTS框架中用于管理组件状态的核心装饰器,其核心作用是实现数据驱动UI的响应式编程模式,本文给大家介绍... 目录一、@State在鸿蒙中是做什么的?二、@Spythontate的基本原理1. 依赖关系的收集2.

Java编译生成多个.class文件的原理和作用

《Java编译生成多个.class文件的原理和作用》作为一名经验丰富的开发者,在Java项目中执行编译后,可能会发现一个.java源文件有时会产生多个.class文件,从技术实现层面详细剖析这一现象... 目录一、内部类机制与.class文件生成成员内部类(常规内部类)局部内部类(方法内部类)匿名内部类二、

Python中随机休眠技术原理与应用详解

《Python中随机休眠技术原理与应用详解》在编程中,让程序暂停执行特定时间是常见需求,当需要引入不确定性时,随机休眠就成为关键技巧,下面我们就来看看Python中随机休眠技术的具体实现与应用吧... 目录引言一、实现原理与基础方法1.1 核心函数解析1.2 基础实现模板1.3 整数版实现二、典型应用场景2

Java的IO模型、Netty原理解析

《Java的IO模型、Netty原理解析》Java的I/O是以流的方式进行数据输入输出的,Java的类库涉及很多领域的IO内容:标准的输入输出,文件的操作、网络上的数据传输流、字符串流、对象流等,这篇... 目录1.什么是IO2.同步与异步、阻塞与非阻塞3.三种IO模型BIO(blocking I/O)NI

JAVA封装多线程实现的方式及原理

《JAVA封装多线程实现的方式及原理》:本文主要介绍Java中封装多线程的原理和常见方式,通过封装可以简化多线程的使用,提高安全性,并增强代码的可维护性和可扩展性,需要的朋友可以参考下... 目录前言一、封装的目标二、常见的封装方式及原理总结前言在 Java 中,封装多线程的原理主要围绕着将多线程相关的操

kotlin中的模块化结构组件及工作原理

《kotlin中的模块化结构组件及工作原理》本文介绍了Kotlin中模块化结构组件,包括ViewModel、LiveData、Room和Navigation的工作原理和基础使用,本文通过实例代码给大家... 目录ViewModel 工作原理LiveData 工作原理Room 工作原理Navigation 工

Java的volatile和sychronized底层实现原理解析

《Java的volatile和sychronized底层实现原理解析》文章详细介绍了Java中的synchronized和volatile关键字的底层实现原理,包括字节码层面、JVM层面的实现细节,以... 目录1. 概览2. Synchronized2.1 字节码层面2.2 JVM层面2.2.1 ente