首页 > ACM题库 > HDU-杭电 > HDU 4407-Sum-DFS-[解题报告]HOJ
2015
05-24

HDU 4407-Sum-DFS-[解题报告]HOJ

Sum

问题描述 :

XXX is puzzled with the question below:

1, 2, 3, …, n (1<=n<=400000) are placed in a line. There are m (1<=m<=1000) operations of two kinds.

Operation 1: among the x-th number to the y-th number (inclusive), get the sum of the numbers which are co-prime with p( 1 <=p <= 400000).
Operation 2: change the x-th number to c( 1 <=c <= 400000).

For each operation, XXX will spend a lot of time to treat it. So he wants to ask you to help him.

输入:

There are several test cases.
The first line in the input is an integer indicating the number of test cases.
For each case, the first line begins with two integers — the above mentioned n and m.
Each the following m lines contains an operation.
Operation 1 is in this format: "1 x y p".
Operation 2 is in this format: "2 x c".

输出:

There are several test cases.
The first line in the input is an integer indicating the number of test cases.
For each case, the first line begins with two integers — the above mentioned n and m.
Each the following m lines contains an operation.
Operation 1 is in this format: "1 x y p".
Operation 2 is in this format: "2 x c".

样例输入:

1
3 3
2 2 3
1 1 3 4
1 2 3 6

样例输出:

7
0

题目链接: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;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/dgq8211/article/details/8031257