HDU-4407-Sum(容斥原理)

HDU-4407-Sum(容斥原理)

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
思路：m<=1000 和 數列初始狀態為1,2,3,..n 是該題的突破口。對於每一次詢問，先不考慮數字被修改了，那我們可以直接用求和公式把x到y之間的數字的和求出來，然後再減去那些不和p互質的數(用容斥原理)，再對修改過的數進行特判即可。

#include 

int num,idx[1005],val[1005],prime[10],p[40000];

inline bool check(int x)
{
    int i;

    for(i=0;ii) p[cnt++]=i;
    }
    //------------------------------------------

    scanf("%d",&T);

    while(T--)
    {
        scanf("%d%d",&n,&m);

        cnt=0;

        for(i=1;i<=m;i++)
        {
            scanf("%d",&type);

            if(type==1)
            {
                scanf("%d%d%d",&a,&b,&c);

                ans=(long long)(a+b)*(b-a+1)/2;

                num=0;//質因數的個數

                //獲取c的質因數-----------------
                last=0;

                while(c>1)
                {
                    if(c%p[last]==0)
                    {
                        prime[num++]=p[last];
                        c/=p[last];
                        while(c%p[last]==0) c/=p[last];
                    }

                    last++;
                }
                //-------------------------------

                //容斥原理-------------------------
                for(j=1;j<(1<