【HDU4135】Co-prime
题意
给出三个整数N,A,B。问在区间[A,B]内，与N互质的数的个数。其中N<=10^9,A,B<=10^15。
分析
容斥定理的模板题。可以通过容斥定理求出[1,n]与x互质的数的个数。方法是先将x进行质因子分解，然后对于每个质因子pi，[1,n]内可以被pi整除的数目为n/pi。可以通过容斥定理解决逆命题，既[1,n]与x不互质的数目。n/p1+n/p2+n/p3-n/p1p2-n/p1p3-n/p2p3+n/p1p2p3。既奇数是加，偶数是减。具体的做法一般是通过二进制枚举来进行。质因子分解N的时间复杂度是O(sqrt(N)),然后枚举质因子的时间复杂度是O(2^(num))，其中num是质因子的数目。我们知道，这个num一般来说是非常小的，所以这个算法的时间复杂度是非常优秀的。
然后对于这个题，我们求出[1,B]与N互质的个数再减去[1,A]互质的个数。
code如下
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream> using namespace std;
typedef long long LL;
int T,N,num;
LL A,B;
int a[];
void prime(int n){
num=;
for(int i=;i*i<=n;i++){
if((n%i)==){
num++;
a[num]=i;
while((n%i)==){
n/=i;
}
}
}
if(n>){
num++;
a[num]=n;
}
return ;
}
LL solve(LL r,int n){
prime(n);
LL res=;
for(int i=;i<(<<num);i++){
int kk=;
LL div=;
for(int j=;j<=num;j++){
if(i&(<<(j-))){
kk++;
div*=a[j];
}
}
if(kk%)
res+=r/div;
else
res-=r/div;
}
return r-res;
}
int main(){
scanf("%d",&T);
for(int t=;t<=T;t++){
scanf("%lld%lld%d",&A,&B,&N);
LL ans=solve(B,N)-solve(A-,N);
printf("Case #%d: %lld\n",t,ans);
}
return ;
}
【HDU2841】visible tree
题意
有一片树林m*n,从（1，1）开始，每个整数点都有一棵树。famer站在点（0，0），问他能看见的树有几棵。其中n,m<=100000.
分析
先来看有哪些树没有办法被看到。对于点(xi,yi)，当xi和yi可以同时被一个大于1的整数k整除，则点（xi,yi)无法被看到。也就是说，当且仅当这个点的横纵坐标互质时，才可以被看到。也就是说求[1,n]和[1,m]内有多少互质的点。到此为止，本题已经转换为上一个题的形式。然后枚举[1,m]作为x,然后[1,n]作为区间，按照上题方案进行求解。
code 如下
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream> using namespace std;
typedef long long LL;
int T,n,m,num;
int a[];
void prime(int x){
num=;
for(int i=;i*i<=x;i++){
if(x%i==){
num++;
a[num]=i;
while(x%i==&&x){
x/=i;
}
}
}
if(x>){
num++;
a[num]=x;
}
return;
}
LL solve(LL r,int x){
LL res=;
for(int i=;i<(<<num);i++){
LL k=,aa=;
for(int j=;j<=num;j++){
if(i&(<<(j-))){
k++;
aa*=a[j];
}
}
if(k%)
res+=r/aa;
else
res-=r/aa;
}
return r-res;
}
int main(){
scanf("%d",&T); for(int t=;t<=T;t++){
scanf("%d%d",&n,&m);
if(n>m)swap(n,m);
LL ans=; for(int i=;i<=n;i++){
prime(i);
ans+=solve(m,i);
//cout<<solve(m,i)<<endl;
}
printf("%lld\n",ans);
}
return ;
}
【HDU1695】GCD
题意
给出a,b,c,d,k，其中保证a=1,c=1。问在区间[a,b]和区间[c,d]内有多少不同的对gcd（x,y)=k。
分析
如果gcd(x,y)=k，则显然gcd(x/k,y/k)=1，既互质。我们令b<d,然后b/=k,d/=k。则题目转化为在区间[1,b]和区间[1,d]有多少不同对互质。
有没有感觉和上面那道题很像？就一个不同点，这个题目求的是不同对。所以不可以按照上面这个题直接进行枚举。对于区间[1,b]，我们可以直接枚举求和欧拉函数。对于区间[b+1,d]我们可以按照上面的方法通过容斥定理进行求解。
code如下
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream> using namespace std;
typedef long long LL; int T,a,b,c,d,k;
LL ans;
int euler(int n){ //返回euler(n)
int res=n,aa=n;
for(int i=;i*i<=aa;i++){
if(aa%i==){
res=res/i*(i-);//先进行除法是为了防止中间数据的溢出
while(aa%i==) aa/=i;
}
}
if(aa>) res=res/aa*(aa-);
return res;
}
int num;
int pri[];
void prime(int x){
num=;
for(int i=;i*i<=x;i++){
if(x%i==){
num++;
pri[num]=i;
while(x%i==){
x/=i;
}
}
}
if(x>){
num++;
pri[num]=x;
}
}
LL solve(LL r,int x){
LL res=;
for(int i=;i<(<<num);i++){
int k=,aa=;
for(int j=;j<=num;j++){
if(i&(<<(j-))){
k++;
aa*=pri[j];
}
}
if(k%)
res+=r/aa;
else
res-=r/aa;
}
return r-res;
}
int main(){
scanf("%d",&T);
for(int t=;t<=T;t++){
scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
if(k==){
printf("Case %d: 0\n",t);
continue;
}
if(b>d)swap(b,d);
b/=k,d/=k;
ans=;
for(int i=;i<=b;i++){
ans+=euler(i);
}
for(LL i=b+;i<=d;i++){
prime(i);
ans+=solve(b,i);
}
printf("Case %d: %lld\n",t,ans);
}
return ;
}