HDU 4407 Sum 解題報告（容斥原理）

Sum

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 1710    Accepted Submission(s): 477

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
0
        

Source 2012 ACM/ICPC Asia Regional Jinhua Online  

    解題報告：至多1000次更改操作，直接暴力處理。求和時使用容斥原理即可，和前幾篇部落格一樣，分解質因數，奇加偶剪。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long LL;

int change[1001];
int newnum[1001];
int changeNum;

int prime[100010];
int primeNum;

LL co_prime_sum(int n, int m)
{
    LL ans = (long long)m*(m+1)/2 - (long long)n*(n-1)/2;
    n--;

    for(int i=1;i<(1<<primeNum);i++)
    {
        int tmp = 1;
        bool flag = false;
        for(int j=0;j<primeNum;j++) if(i&(1<<j))
            tmp *= prime[j], flag = !flag;

        if(flag)
            ans-=((long long)m/tmp*(m/tmp+1)/2 - (long long)(n/tmp)*(n/tmp+1)/2)*tmp;
        else
            ans+=((long long)m/tmp*(m/tmp+1)/2 - (long long)(n/tmp)*(n/tmp+1)/2)*tmp;
    }

    return ans;
}

int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}

void work()
{
    changeNum = 0;

    int n,m;
    scanf("%d%d",&n,&m);

    while(m--)
    {
        int op;
        scanf("%d", &op);
        if(op==1)
        {
            int l,r,p;
            scanf("%d%d%d",&l,&r,&p);

            LL res = 0;
            for(int i=0;i<changeNum;i++) if(change[i]>=l && change[i]<=r)
            {
                if(gcd(change[i], p)==1) res-=change[i];
                if(gcd(newnum[i], p)==1) res+=newnum[i];
            }

            primeNum = 0;
            for(int i=2;i*i<=p;i++) if(p%i==0)
            {
                prime[primeNum++]=i;
                while(p%i==0) p/=i;
            }
            if(p>1) prime[primeNum++]=p;

            res += co_prime_sum(l,r);
            printf("%I64d\n",res);
        }
        else
        {
            int x,v;
            scanf("%d%d",&x,&v);

            bool has = false;
            for(int i=0;i<changeNum;i++) if(change[i]==x)
            {
                has = true;
                newnum[i] = v;
            }
            if(!has)
            {
                change[changeNum] = x;
                newnum[changeNum] = v;
                changeNum++;
            }
        }
    }
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
        work();
}