首页 > 代码库 > hdu 4407 Sum(容斥)
hdu 4407 Sum(容斥)
http://acm.hdu.edu.cn/showproblem.php?pid=4407
起初有n个数1~n,这里有m个操作,两种类型。操作1:求出[x,y]区间内与p互质的数的和。操作2:将第x位置的数变成y。对于每一个询问,输出结果。
因为只有1000次操作,而且起初是有序的。那么对于第i个询问,我们先忽略i之前的所有的第2种操作,即认为n个数为1~n,根据容斥原理求出[x,y]区间内与p互质的数之和,然后遍历i之前的操作2,对所求的答案进行调整即可。wa了无数次,改了好久,是因为我忽略的一点,对x位置的数有可能进行多次修改,我们只需考虑最后一次修改即可。所以可用用map保存一下操作2。
#include <stdio.h> #include <iostream> #include <map> #include <set> #include <bitset> #include <list> #include <stack> #include <vector> #include <math.h> #include <string.h> #include <queue> #include <string> #include <stdlib.h> #include <algorithm> #define LL __int64 //#define LL long long #define eps 1e-9 #define PI acos(-1.0) using namespace std; const int maxn = 400010; int n,m; bool flag[maxn]; int prime[maxn]; int fac[100]; int facCnt; LL ans; map<int,int>M; int gcd(int a, int b) { if(b == 0) return a; return gcd(b,a%b); } void getPrime() { memset(flag,false,sizeof(flag)); prime[0] = 0; for(int i = 2; i < maxn; i++) { if(flag[i] == false) prime[++prime[0]] = i; for(int j = 1; j <= prime[0]&&prime[j]*i < maxn; j++) { flag[prime[j]*i] = true; if(i % prime[j] == 0) break; } } } void getFac(int num) { int tmp = num; facCnt = 0; for(int i = 1; i <= prime[0]&&prime[i]*prime[i] <= tmp; i++) { if(tmp % prime[i] == 0) { fac[facCnt++] = prime[i]; while(tmp % prime[i] == 0) tmp /= prime[i]; } if(tmp == 1) break; } if(tmp > 1) fac[facCnt++] = tmp; } LL getSum(int t) { return ((1 + 1LL * t) * 1LL * t) >> 1; } //求【1,r】内与该数互质的数之和。 LL cal(int r) { LL anw = getSum(r); LL tmp = 0; for(int i = 1; i < (1<<facCnt); i++) { LL mul = 1; int cnt = 0; for(int j = 0; j < facCnt; j++) { if(i&(1<<j)) { mul *= fac[j]; cnt++; } } if(cnt&1) tmp += mul * getSum((LL)r/mul); else tmp -= mul * getSum((LL)r/mul); } return anw - tmp; } int main() { getPrime(); int test; scanf("%d",&test); while(test--) { M.clear(); int op,x,y,z; scanf("%d %d",&n,&m); for(int i = 1; i <= m; i++) { scanf("%d",&op); if(op == 1) { scanf("%d %d %d",&x,&y,&z); getFac(z); ans = cal(y) - cal(x-1); //printf("ans : %I64d\n",ans); map<int,int>::iterator it; for(it = M.begin(); it != M.end(); it++) { if(it->first >= x && it->first <= y) { if(gcd(z,it->first) == 1) ans -= it->first; if(gcd(z,it->second) == 1) ans += it->second; } } printf("%I64d\n",ans); } else { scanf("%d %d",&x,&y); M[x] = y; } } } return 0; }
hdu 4407 Sum(容斥)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。