HDU4407Sum (용 척 원리)

제목 링크:
http://acm.hdu.edu.cn/showproblem.php?pid=4407
제목:
하나의 길이 가 n 인 서열, 시작 하 는 서열 은 1, 2, 3... n 이다.
그리고 또 두 가지 조작.
operation 1: 구간 [a, b] 에서 p 와 서로 질 적 인 수의 합 을 묻는다.
operation 2: 번호 가 i 인 수 를 x 로 변경 합 니 다.
조작 을 수정 하지 않 았 다 면, 분명 한 것 은 용 척 원리 이다.
계산 적 문제.
수정 을 더 했 지만 횟수 가 많 지 않 기 때문에 우 리 는
수 정 된 점 을 기록 한 후에 먼저 숫자 를 기록 한 다음 에 옮 겨 다 닌 다.
기 록 된 배열 은 수 정 된 수 를 더 해 야 하 는 지, 이전의 수 를 판단 한다.
지 울 지 말 지.
코드 는 다음 과 같 습 니 다:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <map>
#include <vector>
using namespace std;

typedef long long LL;

map<int,int > mp;
map<int,int >::iterator it;

vector<int >vc;

void fen(int x){
    vc.clear();
    for(int i=2;i*i<=x;i++){
        if(x%i==0){
            vc.push_back(i);
            while(x%i==0) x/=i;
        }
    }
    if(x>1) vc.push_back(x);
}

LL solve(int x,int p){
    LL ans =(LL)x*(x+1)/2;
    fen(p);
    //cout<<"vc.size() "<<vc.size()<<endl;
    for(int i=1;i<(1<<vc.size());i++){
        int cnt = 0;
        LL tmp = 1;
        for(int j=0;j<vc.size();j++){
            if((1<<j)&i) tmp*=vc[j],cnt++;
        }
        LL k = x/tmp;
        k = (k+1)*k/2*tmp;
        if(cnt%2) ans -= k;
        else ans += k;
    }
    return ans;
}

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

int main()
{
    int t,n,m,ord,x,y,p;
    scanf("%d",&t);
    while(t--){
        mp.clear();
        scanf("%d%d",&n,&m);
        for(int i=0;i<m;i++){
            scanf("%d",&ord);
            if(ord==2){
                scanf("%d%d",&x,&y);
                mp[x]=y;
            }
            else{
                scanf("%d%d%d",&x,&y,&p);
                LL ans = solve(y,p)-solve(x-1,p);
                //printf("ans= %d
",ans);
                for(it=mp.begin();it!=mp.end();it++){
                    if(it->first>=x&&it->first<=y){
                        if(gcd(it->first,p)==1) ans -= it->first;
                        if(gcd(it->second,p)==1) ans +=it->second;
                    }
                }
                printf("%I64d
",ans);
            }
        }
    }
    return 0;
}