# 利用容斥原理求解 [a,b] 区间中与 n 互质的数字个数

2018 年 8 月 8 日 05:32

## 题目描述

HDU 4135 Co-prime

Given a number N, you are asked to count the number of integers between A and B inclusive which are relatively prime to N.
Two integers are said to be co-prime or relatively prime if they have no common positive divisors other than 1 or, equivalently, if their greatest common divisor is 1. The number 1 is relatively prime to every integer.

## 分析

$n$ 不互质的数字都是$n$ 有公共因子的数字。我们可以先将 $n$ 分解质因数，它的质因子肯定不会很多（似乎最多是12个？好像有个公式的……）。

## 代码

#define CLEAR(x) memset(x,0,sizeof(x))
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<vector>
using namespace std;
const int maxn=50;
int T;
long long a,b,n;
vector<long long> yinzi;
long long ret=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9') ret=(long long)ret*10+ch-'0',ch=getchar();
return (long long)ret*f;
}
inline void MakeYinzi(long long n){
yinzi.clear();
for (long long i=2;i*i<=n;i++) if (n%i==0){
yinzi.push_back(i);
while (n%i==0) n/=i;
}
if (n>1) yinzi.push_back(n);
}
inline long long GetAnswer(long long x,long long n){
long long ret=0;
MakeYinzi(n);
long long s=1<<yinzi.size();
for (int i=1;i<s;i++){
long long now=1,cnt=0;
for (long long j=0;j<yinzi.size();j++) if (i&(1<<j)){
now*=yinzi[j];
cnt++;
}
if (cnt&1) ret+=x/now; else ret-=x/now;
}
return x-ret;
}
int main(){
for (int t=1;t<=T;t++){
printf("Case #%d: %lld\n",t,ans);
}
return 0;
}


## 拓展：ZOJ 3547

On Mars, there is a huge company called ACM (A huge Company on Mars), and it’s owned by a younger boss.

Due to no moons around Mars, the employees can only get the salaries per-year. There are n employees in ACM, and it’s time for them to get salaries from their boss. All employees are numbered from 1 to n. With the unknown reasons, if the employee’s work number is k, he can get k^4 Mars dollars this year. So the employees working for the ACM are very rich.

Because the number of employees is so large that the boss of ACM must distribute too much money, he wants to fire the people whose work number is co-prime with n next year. Now the boss wants to know how much he will save after the dismissal.

$\displaystyle \sum_{i=1}^{n} i^4 = \frac {n(n+1)(2n+1)(3n^2+3n+1)} {30}$

#define CLEAR(x) memset(x,0,sizeof(x))
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<vector>
using namespace std;
const int maxn=100;
const long long tt=1e9+7;
const int inv30=233333335;
int T;
long long n;
vector<long long> yinzi;
long long ret=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9') ret=(long long)ret*10+ch-'0',ch=getchar();
return (long long)ret*f;
}
inline void MakeYinzi(int n){
yinzi.clear();
for (int i=2;i*i<=n;i++) if (n%i==0){
yinzi.push_back(i);
while (n%i==0) n/=i;
}
if (n>1) yinzi.push_back(n);
}
inline long long Get4(long long x){
long long ret= (long long)x*(x+1)%tt*(2*x+1)%tt*(3*x*x%tt+3*x%tt-1+tt)%tt;
return ret;
}
inline long long Make(long long x){
long long ret=Get4(n/x);
return x*x%tt*x%tt*x%tt*ret%tt;
}
inline long long GetAnswer(long long n){
MakeYinzi(n);
long long ret=Get4(n);
int s=1<<yinzi.size();
for (int i=1;i<s;i++){
long long now=1,cnt=0;
for (int j=0;j<yinzi.size();j++) if (i&(1<<j)){
now*=yinzi[j];
cnt++;
}
if ((cnt&1)==0) ret=(ret+Make(now))%tt; else ret=(ret-Make(now)+tt)%tt;
}
return (ret*inv30)%tt;
}
int main(){
for (int t=1;t<=T;t++){
printf("%lld\n",ans);
}
return 0;
}