hdu - Sum-4407 - 容斥原理

Problem Description

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.

Input

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”.

Output

For each operation 1, output a single integer in one line representing the result.

Sample Input

1

3 3

2 2 3

1 1 3 4

1 2 3 6

Sample Output

7

Source

2012 ACM/ICPC Asia Regional Jinhua Online

題解

題意

有一個元素為 1~n 的數列{An}，有2種操作（1≤m≤1000次）

1、求某段區間 [a,b] 中與 p 互質的數的和。

2、将數列中某個位置元素的值改變。

思路

• 對于操作2，我們可以用map數組記錄修改的num和修改後的val。
• 對于操作1，因為要求所有與p互質的數的和，我們可以轉換為求sum(x~y)的和減去所有與p不互質的數的和。
  • 求sum(x~y)的和，我們可以直接用等差公式求和即可。即sum(y)-sum(x-1),等差數列公差為1.
  • 求所有與p不互質的和，即有公約數，因為我們隻要知道一個數的質因數，就知道1~n區間内多少與它的約數了，例如12，質因數是2，則有2,4,6,8,10,12共6個，我們可以一次性求掉，因為2+4+6+8+10+12=2*(1+2+3+4+5+6)，利用等差求和2*sum(6)即可，然後就是容斥原理，奇加偶減了。
  • 如果有沒有講清楚的地方，請評論說一下具體的哪裡，感謝您指出我寫題解的不足之處。

代碼

#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
using namespace std;

typedef long long LL;

int fac[];
int cnt;

LL gcd(LL a,LL b)
{//求最大公約數
    return b?gcd(b,a%b):a;
}
void getFactor(LL n)
{//求n的所有素因素
    cnt=;
    LL m=sqrt(n+);
    for(int i=;i<=m&&n;i++){
        if(n%i==){
            fac[cnt++]=i;
            while(n&&n%i==) n/=i;
        }
    }
    if(n>) fac[cnt++]=n;
}
LL getSum(LL n)
{//等差數列求和公式
    return (n+)*n/;//注意(n+1)/2*n這樣不對
}
LL cal(LL n)
{//得到所有與p互質的數之和
    LL res=;
    for(LL i=;i<(L<<cnt);i++){
        LL mult=,ones=;
        for(int j=;j<cnt;j++){
            if(i&(<<j)){
                ones++;
                mult*=fac[j];
            }
        }
        //奇加偶減
        if(ones&) res+=mult*getSum(n/mult);
        else res-=mult*getSum(n/mult);
    }
    //所有與p互質的數之和=整體和-所有與不互質的數之和
    res=getSum(n)-res;
    return res;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        map<LL,LL>mp;
        map<LL,LL>::iterator it;
        LL n,m;
        LL op,x,y,p,c;
        scanf("%lld%lld",&n,&m);
        while(m--){
            scanf("%lld",&op);
            if(op==){
                scanf("%lld%lld",&x,&c);
                mp[x]=c;
            }else{
                scanf("%lld%lld%lld",&x,&y,&p);
                if(x>y) swap(x,y);
                getFactor(p);
                //printf("%lld-%lld",cal(y),cal(x-1));
                LL ans=cal(y)-cal(x-);
                for(it=mp.begin();it!=mp.end();++it)
                {
                    LL num=it->first,val=it->second;
                    if(num<x||num>y) continue;
                    if(gcd(num,p)==){
                        ans-=num;
                        //printf("-%lld",num);
                    }
                    if(gcd(val,p)==){
                        ans+=val;
                        //printf("+%lld",val);
                    }
                }
                //printf("=");
                printf("%lld\n",ans);
            }
        }
    }
    return ;
}