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

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 4135 Co-prime & hdu 2841 Visible Tree & hdu 1695 GCD  

2013-08-02 15:57:14|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://acm.hdu.edu.cn/showproblem.php?pid=1695
这三题的题目很类似,难度递增,都是容斥原理的升级版本的好题,放一起总结了。详细解法见1695的解法。

hdu 4135 Co-prime
从一个给定的区间[a, b]中找出有多少个数和给出的n是互质的,分别先求出区间[1, a-1]和区间[1, b]内有多少个数和n不互质,然后再用a-1和b减下,算出有多少个数和n互质,最后两个结果相减得到区间[a, b]中有多少个数和n互质。

/*
* fudq.cpp
*
* Created on: 2013-08-02
* 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=100010;
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[N];
bool f[N];
int tot,prime[N];

void fun()
{
int 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;
}

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;
}

LL dfs(LL tmp,LL n)
{
LL s=0;
for(LL i=tmp;i<plen;i++)
s=s+n/p[i]-dfs(i+1,n/p[i]);
return s;
}


int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt","r",stdin);
// freopen("testout.txt","w",stdout);
#endif
int T,cas=1;
LL ans,a,b,n,r1,r2;
fun();
scanf("%d",&T);
while(T--)
{
scanf("%I64d%I64d%I64d",&a,&b,&n);
Getfac(n);
r1=a-1-dfs(0,a-1);
r2=b-dfs(0,b);
ans=r2-r1;
printf("Case #%d: %I64d\n",cas++,ans);
}
return 0;
}



hdu 2841 Visible Tree
把问题化简为,从两个区间[1,n]和[1,m]中分别取一个数,这两个数互质,问有多少种取法。

/*
* fudq.cpp
*
* Created on: 2013-08-02
* 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=100010;
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[N];
__int64 prime[N];//存素数
bool f[N];
__int64 Ou[N+2];//存欧拉函数

void fun()
{
//打素数表和欧拉函数表,前N个
__int64 i,j,pNum=0;
memset(f,false,sizeof(f));
Ou[1]=1;
for(i=2;i<=N;i++)
{
if(!f[i])
{
prime[pNum++]=i;
Ou[i]=i-1;
}
for(j=0;j<pNum && prime[j]*i<=N;j++)
{
f[prime[j]*i]=true;
if(i%prime[j]==0)
{
Ou[i*prime[j]]=Ou[i]*prime[j];
break;
}
else
Ou[i*prime[j]]=Ou[i]*(prime[j]-1);
}
}
}

void Getfac(int n)
{
plen=0;
for(int 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;
}

LL dfs(int tmp,int n)
{
LL s=0;
for(int i=tmp;i<plen;i++)
s=s+n/p[i]-dfs(i+1,n/p[i]);
return s;
}


int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt","r",stdin);
// freopen("testout.txt","w",stdout);
#endif
int b,d,T;
LL ans;
fun();
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&b,&d);
if(b > d)
{
b^=d;
d^=b;
b^=d;
}
ans=Ou[1];
for(int i=2;i<=b;i++)
ans=ans+2*Ou[i]; //a=2,b=1 和 a=1,b=2 为不同的两类
for(int i=b+1;i<=d;i++)
{
Getfac(i);
ans=ans+b-dfs(0,b);
}
printf("%I64d\n",ans);
}
return 0;
}



hdu 1695 GCD
题意:
给出两个区间[a, b]和[b, d],还有定值k。问有多少对数满足gcd(x, y)==k,x在区间[a, b]内,y在区间[b, d]内。其中a和c均为1。
题解:
可以把问题化简为:分别从区间[1, b/k]和区间[1, d/k]中取一个数,使两个数互质,问有多少种取法。
假设b<=d,则考虑区间[1, d/k],[1, b/k]部分可以由欧拉函数获得。[b/k+1, d/k]部分,取出一个数x,问区间[1, b/k]内有多少个数与x互质。可以先求出区间[1, b/k]内有多少数tmp和x不互质,于是互质部分即为b/k-tmp。求tmp可以先将x质因数分解,用容斥原理求解=区间中能整除一个质因子的个数 - 区间中能整除两个质因子的个数 + 区间中能整除三个质因子的个数……
k==0时需要特判。*为提高效率,求质因数部分可以打表;前n项欧拉函数和也可以打表。

/*
* fudq.cpp
*
* Created on: 2013-08-02
* 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=100100;
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[N];
__int64 prime[N];//存素数
bool f[N];
__int64 Ou[N+2];//存欧拉函数

void fun()
{
//打素数表和欧拉函数表,前N个
__int64 i,j,pNum=0;
memset(f,false,sizeof(f));
Ou[1]=1;
for(i=2;i<=N;i++)
{
if(!f[i])
{
prime[pNum++]=i;
Ou[i]=i-1;
}
for(j=0;j<pNum && prime[j]*i<=N;j++)
{
f[prime[j]*i]=true;
if(i%prime[j]==0)
{
Ou[i*prime[j]]=Ou[i]*prime[j];
break;
}
else
Ou[i*prime[j]]=Ou[i]*(prime[j]-1);
}
}
}

void Getfac(int n)
{
plen=0;
for(int 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;
}

LL dfs(int tmp,int n)
{
LL s=0;
for(int i=tmp;i<plen;i++)
s=s+n/p[i]-dfs(i+1,n/p[i]);
return s;
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt","r",stdin);
// freopen("testout.txt","w",stdout);
#endif
int a,b,c,d,k,T,cas=1;
LL ans;
fun();
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
printf("Case %d: ",cas++);
if(k == 0)
{
printf("0\n");
continue;
}
b/=k;d/=k;
if(b > d)
{
b^=d;
d^=b;
b^=d;
}
ans=0;
for(int i=1;i<=b;i++)
ans+=Ou[i];
for(int i=b+1;i<=d;i++)
{
Getfac(i);
ans=ans+b-dfs(0,b);
}
printf("%I64d\n",ans);
}
return 0;
}




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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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