Sum

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4424 Accepted Submission(s): 1281

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

3 3

2 2 3

1 1 3 4

1 2 3 6

Sample Output

【题意】

操作一查询并输出[a,b]中与p互质的数的总和，操作二更新pos位置的数值。

【思路】

与非常相似，只不过这次是求和（相当于等差数列），再加上修改数值。

容斥定理的实现有三种做法：1.dfs 2.二进制 3.队列数组。大致意思都是表示出每一种质因子的组成情况，奇数个相加，偶数个相减。

修改数值的话可以用map存一下修改的操作，最后把影响结果的操作拿出来处理一下即可。

【代码】

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #define go(i,a,b) for(int i=a;i<=b;i++)#define og(i,a,b) for(int i=a;i>=b;i--)#define mem(a,b) memset(a,b,sizeof(a))#define Pi acos(-1)#define eps 1e-8using namespace std;typedef long long int ll;map 
                
                  mp;map 
                 
                   ::iterator it;ll num,a,b,fac[1005];ll gcd(ll x,ll y){ return y==0?x:gcd(y,x%y);}void init(ll n){ num=0; for(ll i=2;i*i<=n;i++) { if(n%i==0) { fac[num++]=i; while(n%i==0) n/=i; } } if(n>1) fac[num++]=n;}ll cul(ll m){ ll ans=0; for(ll i=1;i<(1<
                  
                   >=1; } t=m/sum; ll tt=t*(t+1)/2*sum; if(c&1) ans+=tt; else ans-=tt; } return ans;}main(){ ll t; cin>>t; while(t--) { ll n,m; mp.clear(); cin>>n>>m; ll x,pos,p; while(m--) { cin>>x; if(x==1) { cin>>a>>b>>p; init(p); ll sum=(a+b)*(b-a+1)/2-cul(b)+cul(a-1); for(it=mp.begin();it!=mp.end();it++) { if(it->first>=a&&it->first<=b) { if(gcd(it->first,p)==1) sum-=it->first; if(gcd(it->second,p)==1) sum+=it->second; } } cout<
                   
                    <
                    
                     >pos>>p; mp[pos]=p; } } }}