当前位置:编程学习 > C/C++ >>

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的倍数 }】。
其中,XX的倍数可以通过等差公式求得。
对于操作2,由于操作比较少,我们可以保存这些操作,当遇到要求和的时候,我们遍历之前保存的操作,找到在区间中改变的值,对应修改即可。
[cpp]
#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) 
        dfs(i+1,cnt+1,m,n,num*fac[i],x); 
    if(n-1-i >= m-cnt) 
        dfs(i+1,cnt,m,n,num,x); 
//    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 易做图(int a,int b) 

    return b ? 易做图(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(易做图((*it).first,p) == 1) 
                            ans -= (*it).first; 
                        if(易做图((*it).second,p) == 1) 
                            ans += (*it).second; 
                    } 
                printf("%I64d\n",ans); 
            } 
            else 
            { 
                scanf("%d%d",&a,&b); 
                M[a] = b; 
            } 
        } 
  
补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,