HDU 4407 Sum(12年金华网络赛-容斥原理)
题目链接:Click here~~第一道容斥原理的题目。
题意:
有一个元素为 1~n 的数列{An},有2种操作(1000次):
1、求某段区间 [a,b] 中与 p 互质的数的和。
2、将数列中某个位置元素的值改变。
解题思路:
对于操作1,解的性质满足区间减法,则我们只需要考虑如何求 [1,n] 中与 p 互质的数的和即可。
考虑到与 p 互质的数不太好解,于是可以通过先求出与 p 不互质的数的和,然后与总和作差得到。
而一个数 x 若与 p 不互质,当且仅当两者素因子的集合有交集。
设 p 的素因子是{P1,P2,…,Pk},于是与 p 不互质的数的素因子集合可以表示成 {P1} U {P2} U … U {Pk}。
那么与 p 不互质的数的集合可以表示成 W = { P1的倍数 } U { P2的倍数 } U … U { Pk的倍数 }。
其中,{ Pk的倍数 } = { Pk*1 } + { Pk*2 } + … + { Pk*Mk } ( Pk*Mk<=n && Pk*(Mk+1)>n )。
从而,ans = sum{ W }。
于是可以通过容斥原理,求得问题的解。
举个简单的例子,假如 k=2,则 ans = 【sum{ P1的倍数 } + sum{ P2的倍数 } - sum{ P1*P2的倍数 }】。
其中,XX的倍数可以通过等差公式求得。
对于操作2,由于操作比较少,我们可以保存这些操作,当遇到要求和的时候,我们遍历之前保存的操作,找到在区间中改变的值,对应修改即可。
[cpp]
#include <map>
#include <stdio.h>
typedef __int64 LL;
using namespace std;
#define N 650
bool np[N];
int prime[120],fac[9],F_top,p;
LL ans;
void get_prime()
{
int top = -1;
for(int i=2;i<N;i++)
if(!np[i])
{
prime[++top] = i;
for(int j=i+i;j<N;j+=i)
np[j] = true;
}
}
void Div(int n)
{
F_top = 0;
for(int i=0;prime[i]*prime[i]<=n;i++)
{
if(n % prime[i])
continue;
while(n % prime[i] == 0)
n /= prime[i];
fac[F_top++] = prime[i];
}
if(n != 1)
fac[F_top++] = n;
}
LL PreSum(int n)
{
return (LL)n*(n+1)/2;
}
void dfs(int i,int cnt,int m,int n,int num,int x) // C(n,m).
{
if(cnt == m)
{
LL sum = num * PreSum(x/num);
m&1 ? ans -= sum : ans += sum;
return ;
}
if(num*fac[i] <= x)
dfs(i+1,cnt+1,m,n,num*fac[i],x);
if(n-1-i >= m-cnt)
dfs(i+1,cnt,m,n,num,x);
// if(num*fac[i] > x || n-i < m-cnt)
// return ;
// dfs(i+1,cnt+1,m,n,num*fac[i],x);
// dfs(i+1,cnt,m,n,num,x);
}
LL sovle(int n)
{
ans = PreSum(n);
for(int m=1;m<=F_top;m++)
dfs(0,0,m,F_top,1,n);
return ans;
}
int 易做图(int a,int b)
{
return b ? 易做图(b,a%b) : a;
}
int main()
{
int z,n,Q,cmd,a,b;
get_prime();
scanf("%d",&z);
map<int,int> M;
while(z--)
{
M.clear();
scanf("%d%d",&n,&Q);
while(Q--)
{
scanf("%d",&cmd);
if(cmd == 1)
{
scanf("%d%d%d",&a,&b,&p);
Div(p);
ans = sovle(b) - sovle(a-1);
for(map<int,int>::iterator it=M.begin();it!=M.end();it++)
if((*it).first >= a && (*it).first <= b)
{
if(易做图((*it).first,p) == 1)
ans -= (*it).first;
if(易做图((*it).second,p) == 1)
ans += (*it).second;
}
printf("%I64d\n",ans);
}
else
{
scanf("%d%d",&a,&b);
M[a] = b;
}
}
补充:软件开发 , C++ ,