首页 > 代码库 > [容斥原理] hdu 4407 Sum
[容斥原理] hdu 4407 Sum
题目链接:
http://acm.hdu.edu.cn/showproblem.php?pid=4407
Sum
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 1817 Accepted Submission(s): 504
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.
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".
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
Recommend
zhoujiaqi2010 | We have carefully selected several similar problems for you: 4822 4821 4820 4819 4818
题目意思:
开始有1~n的n(n<=40000)个数,有两种操作
操作1: 1 x y p 求在区间[x,y]之间和p互质的所有数的和
操作2: 2 x c 把x位置上的数改成c
解题思路:
简单容斥原理
实际上题目要求的就是求1~x间和p互质的数的总和。可以先把p分解质因数,然后用容斥原理求出与p不互质的总和,用总和减去即可。
至于改变,只需保存改变的数值,然后对每个查询扫一遍,单独处理改变的就行了。
代码:
//#include<CSpreadSheet.h> #include<iostream> #include<cmath> #include<cstdio> #include<sstream> #include<cstdlib> #include<string> #include<string.h> #include<cstring> #include<algorithm> #include<vector> #include<map> #include<set> #include<stack> #include<list> #include<queue> #include<ctime> #include<bitset> #include<cmath> #define eps 1e-6 #define INF 0x3f3f3f3f #define PI acos(-1.0) #define ll __int64 #define LL long long #define lson l,m,(rt<<1) #define rson m+1,r,(rt<<1)|1 #define M 1000000007 //#pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std; #define Maxn 410000 bool isp[Maxn]; ll pri[Maxn],pp[Maxn],cnt0,cnt; ll x,y; ll ans1,ans2; map<int,int>myp; int cc,n,m,p; struct Cha { int old,ne; }cha[1100]; void init() //打质数表 { cnt=0; int N=400000; for(int i=1;i<=N;i++) isp[i]=true; for(int i=2;i<=N;i++) { if(isp[i]) { pri[++cnt]=i; for(int j=i*2;j<=N;j+=i) isp[j]=false; } } } void cal(ll cur) //分解质因数 { cnt0=0; for(int i=1;pri[i]*pri[i]<=cur;i++) { if(!(cur%pri[i])) { pp[++cnt0]=pri[i]; while(!(cur%pri[i])) cur/=pri[i]; } } if(cur!=1) pp[++cnt0]=cur; } void dfs(ll hav,int cur,int num) //容斥原理求出不互质的 { if((hav>x&&hav>y)||cur>cnt0) return ; for(int i=cur;i<=cnt0;i++) { ll next=hav*pp[i]; ll tt1=y/next,tt2=x/next; if(num&1) { ans1-=(1+tt1)*tt1/2*next; ans2-=(1+tt2)*tt2/2*next; } else { ans1+=(1+tt1)*tt1/2*next; ans2+=(1+tt2)*tt2/2*next; } dfs(next,i+1,num^1); } } ll gcd(ll a,ll b) { if(a%b==0) return b; return gcd(b,a%b); } int main() { //printf("%I64d\n",gcd(12,18)); //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); init(); int t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); myp.clear(); cc=0; while(m--) { int a; scanf("%d",&a); if(a==1) { scanf("%I64d%I64d%I64d",&x,&y,&p); if(x>y) swap(x,y); x--; //注意x要减一 cal(p); ll ans; ans1=(1+y)*y/2,ans2=(1+x)*x/2; for(int i=1;i<=cnt0;i++) { ll tt1=y/pp[i],tt2=x/pp[i]; ans1-=(1+tt1)*tt1/2*pp[i]; ans2-=(1+tt2)*tt2/2*pp[i]; dfs(pp[i],i+1,0); } ans=ans1-ans2; for(int i=1;i<=cc;i++) { if(cha[i].ne!=cha[i].old&&cha[i].old<=y&&cha[i].old>x) //要在[x,y]范围内找,x已经减了1 { if(gcd(cha[i].old,p)==1) //之前已经加了 ans-=cha[i].old; if(gcd(cha[i].ne,p)==1) //改了过后是否要加上 ans+=cha[i].ne; } } printf("%I64d\n",ans); } else { scanf("%d%d",&x,&y); if(myp.find(x)==myp.end()) { ++cc; myp[x]=cc; cha[cc].ne=y,cha[cc].old=x; } else cha[myp[x]].ne=y; } } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。