题目链接:Click here~~
第一道容斥原理的题目。
题意:
有一个元素为 1~n 的数列{An},有2种操作(1000次):
1、求某段区间 [a,b] 中与 p 互质的数的和。
2、将数列中某个位置元素的值改变。
解题思路:
对于操作1,解的性质满足区间减法,则我们只需要考虑如何求 [1,n] 中与 p 互质的数的和即可。
考虑到与 p 互质的数不太好解,于是可以通过先求出与 p 不互质的数的和,然后与总和作差得到。
而一个数 x 若与 p 不互质,当且仅当两者素因子的集合有交集。
设 p 的素因子是{P1,P2,…,Pk},于是与 p 不互质的数的素因子集合可以表示成 {P1} U {P2} U … U {Pk}。
那么与 p 不互质的数的集合可以表示成 W ={ P1的倍数 } U { P2的倍数 } U … U { Pk的倍数 }。
其中,{ Pk的倍数 } = { Pk*1 } + { Pk*2 } + … + { Pk*Mk } ( Pk*Mk<=n && Pk*(Mk+1)>n )。
从而,ans = sum{ W }。
于是可以通过容斥原理,求得问题的解。
举个简单的例子,假如 k=2,则 ans = 【sum{ P1的倍数 } + sum{ P2的倍数 } - sum{ P1*P2的倍数 }】。其中,某个sum{ }可以通过等差公式求得。
对于操作2,由于操作比较少,我们可以保存这些操作,当遇到要求和的时候,我们遍历之前保存的操作,找到在区间中改变的值,对应修改即可。
#include <map>
#include <stdio.h>
typedef __int64 LL;
using namespace std;
#define N 650
bool np[N];
int prime[120],fac[9],F_top,p;
LL ans;
void get_prime()
{
int top = -1;
for(int i=2;i<N;i++)
if(!np[i])
{
prime[++top] = i;
for(int j=i+i;j<N;j+=i)
np[j] = true;
}
}
void Div(int n)
{
F_top = 0;
for(int i=0;prime[i]*prime[i]<=n;i++)
{
if(n % prime[i])
continue;
while(n % prime[i] == 0)
n /= prime[i];
fac[F_top++] = prime[i];
}
if(n != 1)
fac[F_top++] = n;
}
LL PreSum(int n)
{
return (LL)n*(n+1)/2;
}
void dfs(int i,int cnt,int m,int n,int num,int x) // C(n,m).
{
if(cnt == m)
{
LL sum = num * PreSum(x/num);
m&1 ? ans -= sum : ans += sum;
return ;
}
if(num*fac[i] > x || n-i < m-cnt)
return ;
dfs(i+1,cnt+1,m,n,num*fac[i],x);
dfs(i+1,cnt,m,n,num,x);
}
LL sovle(int n)
{
ans = PreSum(n);
for(int m=1;m<=F_top;m++)
dfs(0,0,m,F_top,1,n);
return ans;
}
int gcd(int a,int b)
{
return b ? gcd(b,a%b) : a;
}
int main()
{
int z,n,Q,cmd,a,b;
get_prime();
scanf("%d",&z);
map<int,int> M;
while(z--)
{
M.clear();
scanf("%d%d",&n,&Q);
while(Q--)
{
scanf("%d",&cmd);
if(cmd == 1)
{
scanf("%d%d%d",&a,&b,&p);
Div(p);
ans = sovle(b) - sovle(a-1);
for(map<int,int>::iterator it=M.begin();it!=M.end();it++)
if((*it).first >= a && (*it).first <= b)
{
if(gcd((*it).first,p) == 1)
ans -= (*it).first;
if(gcd((*it).second,p) == 1)
ans += (*it).second;
}
printf("%I64d\n",ans);
}
else
{
scanf("%d%d",&a,&b);
M[a] = b;
}
}
}
return 0;
}
分享到:
相关推荐
"hdu 1695 GCD(欧拉函数+容斥原理)" 题目大意是:给定 a, b, c, d, k,找到一队 x, y,满足 g(x, y) = k,且 x ∈ [1, b], y ∈ [1, d],问有多少对符合要求的 (x, y)。 思路是:gcd(x, y) == k 解释 x, y 都能...
标题中的“HDU数据库单元原理(Oracle)”是指在华为的HLR(Home Location Register)系统中,关于数据库单元的设计和实现原理,特别是基于Oracle数据库系统的部分。HLR是移动通信网络中的核心组件,用于存储用户的...
5. **算法**:报告涵盖的算法可能包括排序(快速排序、归并排序、冒泡排序等)、查找(二分查找、哈希查找)、图论算法(最短路径、最小生成树)、组合数学(排列组合、鸽巢原理、容斥原理)等。 6. **编程技巧**:...
这份"HDU杭电 计算机网络实验报告"压缩包提供了丰富的实验材料,涵盖了多个关键的网络技术,包括交换机配置、路由协议、地址转换(NAT)、访问控制列表(ACL)以及动态主机配置协议(DHCP)等。以下是这些实验报告所...
数学在ACM竞赛中扮演着重要角色,包括数论(模运算、同余方程、欧几里得算法等)、组合数学(排列组合、容斥原理、鸽巢原理等)、图论(网络流、最大匹配等)。理解并运用这些数学知识,可以解决很多看似复杂的问题...
hdu 期末考试复习资料 计算机网络 编译原理 计算机图形学 编译原理 信息安全与技术 数据库应用系统开发
在本话题中,我们关注的是一个名为"HDU-EID-V2-核心板1"的特定设计,它涉及到STM32的核心组件、接口、电源管理和调试配置。 首先,核心板设计中提到了F103和F207两个型号的STM32芯片。F103和F207属于STM32的不同...
杭电acm1297 #include<stdio.h> #include<string.h> #define m 1002 int f[m][70]={{1,1},{1,1},{1,2},{1,4}} void add(int p[],int q[],int sum[]) ...=10000){sum[i]-=10000 sum[i+1]++ } }
7. **组合数学**:排列组合、鸽巢原理、容斥原理、卡特兰数、斯特林数等。 8. **概率统计**:随机化算法,如Monte Carlo方法。 每个解题报告都会包含以下部分: - **问题描述**:阐述了问题的具体要求和输入输出...
### hdu1250高精度加法 #### 背景介绍 在计算机科学与编程竞赛中,处理大整数运算(特别是加法、减法、乘法等)是常见的需求之一。当数字的位数超过了标准数据类型(如`int`、`long`等)所能表示的最大值时,就需要...
2-sat---hdu3062,代码详尽,清晰,格式规范,亲测无误。
而HDU作为国内知名的在线编程竞赛平台,其举办的多校训练赛则为参赛者提供了丰富的实战机会。2019年第六场赛事,无疑是这一年度中的一次亮点,选手们在这里挑战自我,不断突破技术瓶颈。 这次比赛的资料包中包含了...
【标题】"hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj" 提供的信息是关于一个压缩文件,其中包含了一个名为 "HDU 1089.cpp" 的源代码文件,这个文件是为了解决杭州电子科技大学(Hangzhou Dianzi ...
示例 1:示例 2:解答:大小写转换: n = n ^ 32转小写: n = n | 32转大写: n = n & -33const toLowerCase =
4. **数学应用**:很多ACM题目需要应用到基础数学知识,例如数论(模运算、最大公约数、最小公倍数)、组合数学(排列组合、容斥原理)、概率论等。 5. **贪心策略**:部分题目可以通过贪心算法求解,即每次做出...
从第 1 秒开始,每 一秒最 开始 时,每个数据服务器都会检查它是否收到了主服务器的回复信息(包括新发出信息的回复信息):如果还没收到任何回复信息,那么该服务器
【标题】"HDU_2010.rar"是一个压缩包文件,其中包含了与"HDU 2010"相关的资源,特别是针对"HDU ACM20"比赛的编程题目。"hdu 2010"和"hdu 20"可能是该比赛的不同简称或分类,而"hdu acm20"可能指的是该赛事的第20届...
这个名为"HDU-2000-2099.rar_hdu"的压缩包包含了该平台从2000到2099共100道题目的源代码。这些题目涵盖了初级到高级的各种算法,对于学习和提升编程技能非常有帮助。 首先,我们来看看这些题目可能涉及到的基础知识...