注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 4407 Sum  

2013-08-03 14:52:35|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://acm.hdu.edu.cn/showproblem.php?pid=4407
题意:给出一个1到n的序列,然后m种操作,操作分两类,一种是给出区间[x, y]和数p,求区间内与p互质的数之和;两一种是给出两个数x, p,把第x个数用p代替。
题解:
因为操作的总数不多,所以先把第二种操作保存。对于第一种操作,可以先求出区间[1, x-1]和区间[1, y]内与数p互质之和,最后得到的两个结果相减便得到了区间[x, y]和数p互质的数之和。求区间[1, a]内与数p互质之和,可以先求与数p不互质之和,先求出数p的所有质因子,然后用容斥原理求,加上能被一个因子整除的所有数,减去能被两个因子整除的所有数……这样算出区间[x, y]和数p互质的数之和后,还要处理第一种操作的数,如果原来数a满足gcd(a, p)==1,则应该减去a,如果现在的数b满足gcd(b, p)==1,则应该加上b。
写代码还要再仔细些,WA了好几次,在Discuss里看到一组比较好的数据(如下),debug完后发现好几处地方写错了。
/*
1
130 5
1 1 130 26
2 13 58
1 1 130 39
1 39 130 130
1 41 141 1
*/
对应结果应该是:
3900
5254
2852
9191

/*
* fudq.cpp
*
* Created on: 2013-08-03
* Author: fudq
*/
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <functional>
#include <numeric>
#include <cctype>
using namespace std;

#define FOR(i,a) for((i)=0;i<(a);(i)++)
#define MEM(a) (memset((a),0,sizeof(a)))
#define LL __int64

const int N=400010;
const int M=1000010;
const int MOD=1000000007ll;
const int INF=0x7fffffff;
const double eps=1e-7;
const double PI=acos(-1.0);

LL plen,p[30];
bool f[N];
LL tot,prime[N];
LL ans;
map<LL,LL> mm;

//打素数表
void fun()
{
LL i,j,s;
memset(f,true,sizeof(f));
f[1]=false;
tot=0;
prime[tot++]=2;
for(i=4;i<=N;i+=2)
f[i]=false;
for(i=3;i*i<=N;i+=2)
{
if(!f[i])
continue;
prime[tot++]=i;
for(s=2*i,j=i*i;j<=N;j+=s)
f[j]=false;
}
for(;i<=N;i++)
if(f[i])
prime[tot++]=i;
}

//求数n的质因子
void Getfac(LL n)
{
plen=0;
for(LL i=0;prime[i]*prime[i] <= n ;i++)
{
if(n%prime[i] == 0)
{
p[plen++]=prime[i];
while(n%prime[i] == 0)
n/=prime[i];
}
if(n == 1)
break;
}
if(n > 1)
p[plen++]=n;
}

//容斥原理求区间[1, n]与p不互质之和
void dfs(LL tmp,LL num,LL c,LL n)
{
LL t,tt;
for(LL i=tmp;i<plen;i++)
{
if(num*p[i] <= n)
{
tt=num*p[i];
t=n/tt;
t=tt*t+t*(t-1)/2*tt;
if((c+1) & 1)
ans+=t;
else
ans-=t;
dfs(i+1,num*p[i],c+1,n);//i写成tmp,WA
}
}
}

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

void work(LL x,LL y,LL p)
{
LL r1,r2,s=0;
Getfac(p);
//处理所有被修改的值
map<LL,LL>::iterator it;
for(it=mm.begin();it!=mm.end();it++)
{
if(it->first == it->second || it->first > y || it->first < x)//后面一个first写成second,WA
continue;
if(gcd(it->first,p)==1)
s-=it->first;
if(gcd(it->second,p)==1)
s+=it->second;
}

ans=0;dfs(0,1,0,x-1);
r1=(LL)x*(x-1)/2-ans;
ans=0;dfs(0,1,0,y);
r2=(LL)y*(y+1)/2-ans;
printf("%I64d\n",s+r2-r1);//r2-r1写成r2+r1,WA
}


int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt","r",stdin);
// freopen("testout.txt","w",stdout);
#endif
fun();
LL t,n,m,x,y,p,a;
scanf("%I64d",&t);
while(t--)
{
mm.clear();
scanf("%I64d%I64d",&n,&m);
while(m--)
{
scanf("%I64d",&a);
if(a == 1)
{
scanf("%I64d%I64d%I64d",&x,&y,&p);
work(x,y,p);
}
else
{
scanf("%I64d%I64d",&x,&p);
mm[x]=p;
}
}
}
return 0;
}



  评论这张
 
阅读(95)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017