`
lovnet
  • 浏览: 6865576 次
  • 性别: Icon_minigender_1
  • 来自: 武汉
文章分类
社区版块
存档分类
最新评论

HDU 4407 Sum(12年金华网络赛-容斥原理)

 
阅读更多

题目链接: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(欧拉函数+容斥原理).docx

    "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)-20081121-B-1.0

    标题中的“HDU数据库单元原理(Oracle)”是指在华为的HLR(Home Location Register)系统中,关于数据库单元的设计和实现原理,特别是基于Oracle数据库系统的部分。HLR是移动通信网络中的核心组件,用于存储用户的...

    ACM HDU 2000-2099 解题报告 杭电 ACM

    5. **算法**:报告涵盖的算法可能包括排序(快速排序、归并排序、冒泡排序等)、查找(二分查找、哈希查找)、图论算法(最短路径、最小生成树)、组合数学(排列组合、鸽巢原理、容斥原理)等。 6. **编程技巧**:...

    HDU杭电 计算机网络实验报告

    这份"HDU杭电 计算机网络实验报告"压缩包提供了丰富的实验材料,涵盖了多个关键的网络技术,包括交换机配置、路由协议、地址转换(NAT)、访问控制列表(ACL)以及动态主机配置协议(DHCP)等。以下是这些实验报告所...

    HDU acm-PPT课件

    数学在ACM竞赛中扮演着重要角色,包括数论(模运算、同余方程、欧几里得算法等)、组合数学(排列组合、容斥原理、鸽巢原理等)、图论(网络流、最大匹配等)。理解并运用这些数学知识,可以解决很多看似复杂的问题...

    hdu 期末考试复习资料 计算机网络 编译原理 计算机图形学等

    hdu 期末考试复习资料 计算机网络 编译原理 计算机图形学 编译原理 信息安全与技术 数据库应用系统开发

    HDU-EID-V2-核心板1

    在本话题中,我们关注的是一个名为"HDU-EID-V2-核心板1"的特定设计,它涉及到STM32的核心组件、接口、电源管理和调试配置。 首先,核心板设计中提到了F103和F207两个型号的STM32芯片。F103和F207属于STM32的不同...

    hdu1297.rar_SUM_hdu1297

    杭电acm1297 #include&lt;stdio.h&gt; #include&lt;string.h&gt; #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]++ } }

    HDU+2000-2099+解题报告

    7. **组合数学**:排列组合、鸽巢原理、容斥原理、卡特兰数、斯特林数等。 8. **概率统计**:随机化算法,如Monte Carlo方法。 每个解题报告都会包含以下部分: - **问题描述**:阐述了问题的具体要求和输入输出...

    hdu1250高精度加法

    ### hdu1250高精度加法 #### 背景介绍 在计算机科学与编程竞赛中,处理大整数运算(特别是加法、减法、乘法等)是常见的需求之一。当数字的位数超过了标准数据类型(如`int`、`long`等)所能表示的最大值时,就需要...

    2-sat---hdu3062

    2-sat---hdu3062,代码详尽,清晰,格式规范,亲测无误。

    2019 Multi-University Training Contest 4(2019hdu多校第六场数据与标程)rar

    而HDU作为国内知名的在线编程竞赛平台,其举办的多校训练赛则为参赛者提供了丰富的实战机会。2019年第六场赛事,无疑是这一年度中的一次亮点,选手们在这里挑战自我,不断突破技术瓶颈。 这次比赛的资料包中包含了...

    hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj

    【标题】"hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj" 提供的信息是关于一个压缩文件,其中包含了一个名为 "HDU 1089.cpp" 的源代码文件,这个文件是为了解决杭州电子科技大学(Hangzhou Dianzi ...

    HDU-Coder-X#Daily-question-of-Leetcode#2021-12-12-709. 转换成小写字母1

    示例 1:示例 2:解答:大小写转换: n = n ^ 32转小写: n = n | 32转大写: n = n & -33const toLowerCase =

    杭电ACMhdu1163

    4. **数学应用**:很多ACM题目需要应用到基础数学知识,例如数论(模运算、最大公约数、最小公倍数)、组合数学(排列组合、容斥原理)、概率论等。 5. **贪心策略**:部分题目可以通过贪心算法求解,即每次做出...

    HDU-Coder-X#Daily-question-of-Leetcode#2022-03-20-2039. 网络空闲的时刻1

    从第 1 秒开始,每 一秒最 开始 时,每个数据服务器都会检查它是否收到了主服务器的回复信息(包括新发出信息的回复信息):如果还没收到任何回复信息,那么该服务器

    HDU_2010.rar_hdu 2010_hdu 20_hdu acm20

    【标题】"HDU_2010.rar"是一个压缩包文件,其中包含了与"HDU 2010"相关的资源,特别是针对"HDU ACM20"比赛的编程题目。"hdu 2010"和"hdu 20"可能是该比赛的不同简称或分类,而"hdu acm20"可能指的是该赛事的第20届...

    HDU-2000-2099.rar_hdu

    这个名为"HDU-2000-2099.rar_hdu"的压缩包包含了该平台从2000到2099共100道题目的源代码。这些题目涵盖了初级到高级的各种算法,对于学习和提升编程技能非常有帮助。 首先,我们来看看这些题目可能涉及到的基础知识...

Global site tag (gtag.js) - Google Analytics