hdu4407(容斥原理)

2024-09-09 17:18
文章标签 原理 容斥 hdu4407

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

题意:给一串数字1,2,......n,两个操作:1、修改第k个数字,2、查询区间[l,r]中与n互质的数之和。

解题思路:咱一看,像线段树,但是如果用线段树做,那么每个区间一定要记录所有的素因子,这样会超内存。然后我就做不来了。后来看了题解,原来是用容斥原理来做的。还记得这道题目吗?求区间[1,r]中与p互质的数的个数,如果不会的话就先去做那题吧。现在这题是求区间[l,r]中与n互质的数的和,先求[1,r]中与n不互质的数字的和,然后做差求与n互质的数的和。由于更新操作只有1000次,所以暴力判断在区间[l,r]内更新过的点。时间复杂度是多少呢,运算比较复杂,但是可以证明时间复杂度并不高。

代码如下:

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<math.h>
#include<cstring>
#include<string>
#include<vector>
#include<map>#define LL __int64
#define N 450000
#define inf 0x3f3f3f3f
#define pi acos(-1.0)
#define eps 10e-6using namespace std;
int pri[N],tot,vis[N];
vector<int> q;
map<int,int> mp;
map<int,int>::iterator it;
void get_primes()
{memset(vis,0,sizeof(vis));tot = 0;int i,m = sqrt(N+0.5);for(i = 2; i <= m; i++){if(vis[i] == 0) pri[tot++] = i;for(LL j = 1LL*i*i; j <= m; j+=i)vis[j] = 1;}
}
void get_primes_of_n(int n)
{q.clear();int i;for(i = 0; i < tot && pri[i]*pri[i] <= n; i++){if(n%pri[i] == 0){q.push_back(pri[i]);while(n%pri[i] == 0)n /= pri[i];}}if(n > 1)   q.push_back(n);
}
LL get_sum(int n)
{int len = q.size();int m = (1<<len);LL ans = 0;int i,j;for(i = 1; i < m; i++){int cnt = 0,a0 = 1;for(j = 0; j < len; j++)if(i&(1<<j)){cnt++;a0 *= q[j];}int k = n/a0;int an = a0+a0*(k-1);LL sum = 1LL*(an+a0)*k/2;if(cnt&1)  //+ans += sum;else ans -= sum;}return ans;
}
int gcd(int a,int b)//  a<b
{return b%a == 0 ? a : gcd(b%a,a);
}int main()
{get_primes();int t;scanf("%d",&t);while(t--){int n,m;scanf("%d%d",&n,&m);mp.clear();while(m--){int op;scanf("%d",&op);if(op == 2){int x,c;scanf("%d%d",&x,&c);mp[x] = c;}else{int x,y,p;scanf("%d%d%d",&x,&y,&p);get_primes_of_n(p);//得到p的质因子LL ans = 1LL*(x+y)*(y-x+1)/2;LL temp = get_sum(y)-get_sum(x-1);ans -= temp;for(it = mp.begin(); it != mp.end(); it++){if(it->first < x || it->first > y)  continue;int k1 = p,k2 = it->first;if(k1 > k2) swap(k1,k2);if(gcd(k1,k2) == 1)ans -= it->first;k1 = p;k2 = it->second;if(k1 > k2) swap(k1,k2);if(gcd(k1,k2) == 1)   ans += it->second;}printf("%I64d\n",ans);}}}return 0;
}


这篇关于hdu4407(容斥原理)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

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

MySQL的隐式锁(Implicit Lock)原理实现

《MySQL的隐式锁(ImplicitLock)原理实现》MySQL的InnoDB存储引擎中隐式锁是一种自动管理的锁,用于保证事务在行级别操作时的数据一致性和安全性,本文主要介绍了MySQL的隐式锁... 目录1. 背景:什么是隐式锁?2. 隐式锁的工作原理3. 隐式锁的类型4. 隐式锁的实现与源代码分析4

MySQL中Next-Key Lock底层原理实现

《MySQL中Next-KeyLock底层原理实现》Next-KeyLock是MySQLInnoDB存储引擎中的一种锁机制,结合记录锁和间隙锁,用于高效并发控制并避免幻读,本文主要介绍了MySQL中... 目录一、Next-Key Lock 的定义与作用二、底层原理三、源代码解析四、总结Next-Key L

Spring Cloud Hystrix原理与注意事项小结

《SpringCloudHystrix原理与注意事项小结》本文介绍了Hystrix的基本概念、工作原理以及其在实际开发中的应用方式,通过对Hystrix的深入学习,开发者可以在分布式系统中实现精细... 目录一、Spring Cloud Hystrix概述和设计目标(一)Spring Cloud Hystr

MySQL中的MVCC底层原理解读

《MySQL中的MVCC底层原理解读》本文详细介绍了MySQL中的多版本并发控制(MVCC)机制,包括版本链、ReadView以及在不同事务隔离级别下MVCC的工作原理,通过一个具体的示例演示了在可重... 目录简介ReadView版本链演示过程总结简介MVCC(Multi-Version Concurr

Redis主从/哨兵机制原理分析

《Redis主从/哨兵机制原理分析》本文介绍了Redis的主从复制和哨兵机制,主从复制实现了数据的热备份和负载均衡,而哨兵机制可以监控Redis集群,实现自动故障转移,哨兵机制通过监控、下线、选举和故... 目录一、主从复制1.1 什么是主从复制1.2 主从复制的作用1.3 主从复制原理1.3.1 全量复制

Redis主从复制的原理分析

《Redis主从复制的原理分析》Redis主从复制通过将数据镜像到多个从节点,实现高可用性和扩展性,主从复制包括初次全量同步和增量同步两个阶段,为优化复制性能,可以采用AOF持久化、调整复制超时时间、... 目录Redis主从复制的原理主从复制概述配置主从复制数据同步过程复制一致性与延迟故障转移机制监控与维

SpringCloud配置动态更新原理解析

《SpringCloud配置动态更新原理解析》在微服务架构的浩瀚星海中,服务配置的动态更新如同魔法一般,能够让应用在不重启的情况下,实时响应配置的变更,SpringCloud作为微服务架构中的佼佼者,... 目录一、SpringBoot、Cloud配置的读取二、SpringCloud配置动态刷新三、更新@R