HDU 4407 Sum [容斥+等差数列求和]

$Sum$Sum

$Description$Description
有一个元素为 1~n 的数列{An}，有2种操作（1≤m≤1000次）
1、求某段区间 [a,b] 中与 p 互质的数的和。
2、将数列中某个位置元素的值改变。

$最初想法$最初想法
使用带修莫队即可.
出于正在做容斥专题, 所以下文主要说 容斥 做法.

对于每个 查询操作, 转化为求 $[1,x]$[1,x]内与 $p$p 不互质的数的和,
首先对 $p$p 分解质因数, 时间复杂度 $O\left(N^{\frac{1}{4}}\right)$O(N41​) .
再使用 容斥 求出 $[1,x]$[1,x] 内与 $p$p 不互质数的和 $Tmp\_1$Tmp_1,
具体地说:
对于容斥中的一项, $\lfloor \frac{x}{p_1}\rfloor$⌊p1​x​⌋ 为 等差数列的项数, 设为 $n$n, 首项, 公差 都是 $p_1$p1​,
则其对答案贡献为 $n\ast p_1+\frac{n\ast (n-1)}{2}\ast p_1$n∗p1​+2n∗(n−1)​∗p1​ .
此时再扫描前方的修改操作, 若 $a-\>b$a−>b, 且在 $[1,x]$[1,x] 区间内, $O\left(logN\right)$O(logN) 判断其是否与 $p$p互质,
减去 $a$a 的贡献, 加上 $b$b 的贡献, 存到 $Tmp\_2$Tmp_2 中, 时间复杂度 $O\left(M\right)\ast O\left(logN\right)$O(M)∗O(logN) .
最后该询问答案即为 $\frac{(1+x)\ast x}{2}-Tmp\_1+Tmp\_2$2(1+x)∗x​−Tmp_1+Tmp_2.

$正解部分$正解部分
如上.

#include<cstdio>
#include<cctype>
#include<cctype>
#include<queue>
#define reg register
typedef long long ll;

int read(){
        char c;
        int s = 0, flag = 1;
        while((c=getchar()) && !isdigit(c))
                if(c == '-'){ flag = -1, c = getchar(); break ; }
        while(isdigit(c)) s = s*10 + c-'0', c = getchar();
        return s * flag;
}

const int maxn = 400005;

int N;
int M;
int p_cnt;
int op_cnt;
int pm[maxn];
int Op[2][maxn];

ll Tmp_1;
ll Tmp_2;

bool Used[maxn];

int Gcd(int a, int b){ return !b?a:Gcd(b, a%b); }
int Lcm(int a, int b){ return a/Gcd(a, b) * b; }

void Div(int p){
        p_cnt = 0;
        for(reg int d = 2; d*d <= p; d ++){
                if(p % d) continue ;
                pm[++ p_cnt] = d;
                while(p%d == 0) p /= d;
        }
        if(p > 1) pm[++ p_cnt] = p;
} 

ll Calc(int x){
        Tmp_1 = 0;
        for(reg int i = 1; i < 1<<p_cnt; i ++){
                int select_num = 0, s_sum = 1;
                for(reg int j = 1; j <= p_cnt; j ++)
                        if((1<<j-1) & i){
                                select_num ^= 1;
                                s_sum = Lcm(s_sum, pm[j]);
                        }
                ll n = x/s_sum;
                if(select_num & 1) Tmp_1 += n*s_sum + n*(n-1)/2 * 1ll*s_sum;
                else Tmp_1 -= n*s_sum + n*(n-1)/2 * 1ll*s_sum;
        }
        //printf("Tmp_1: %lld\n", Tmp_1);
        return (1ll+1ll*x)*x/2 - Tmp_1;
}

void Work(){
        int opt = read();
        if(opt == 2){
                int x = read(), c = read();
                Op[0][++ op_cnt] = x; Op[1][op_cnt] = c;
                return ;
        }
        int x = read(), y = read(), p = read();
        if(x > y) std::swap(x, y);
        Div(p); // ~
// printf("L: %lld R: %lld\n", Calc(y), Calc(x-1));
        ll Ans = Calc(y) - Calc(x-1);

        std::queue <int> Q; Tmp_2 = 0;
        for(reg int i = op_cnt; i >= 1; i --){
                int a = Op[0][i], b = Op[1][i];
                if(x <= a && a <= y && !Used[a]){
                        Used[a] = 1; Q.push(a);
                        Tmp_2 -= (Gcd(a, p)==1) * a;
                        Tmp_2 += (Gcd(b, p)==1) * b;
                }
        }
        while(!Q.empty()){
                int ft = Q.front(); Q.pop();
                Used[ft] = 0;
        }
        printf("%lld\n", Ans+Tmp_2);
}

int main(){
        freopen("a.in", "r", stdin);
        freopen("a.out", "w", stdout);
        int T = read();
        while(T --){
                N = read(), M = read();
                op_cnt = 0;
                while(M --) Work();
        }
        return 0;
}