HDU4135 Co-prime【容斥原理】3方法
程序员文章站
2024-02-11 13:32:16
...
Problem Description
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.
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.
Input
The first line on input contains T (0 < T <= 100) the number of test cases, each of the next T lines contains three integers A, B, N where (1 <= A <= B <= 1015) and (1 <=N <= 109).
Output
For each test case, print the number of integers between A and B inclusive which are relatively prime to N. Follow the output format below.
Sample Input
2 1 10 2 3 15 5
Sample Output
Case #1: 5 Case #2: 10
Hint
In the first test case, the five integers in range [1,10] which are relatively prime to 2 are {1,3,5,7,9}.
题意：计算从a到b中与n的共同因子只有1的数字个数。
思路：欧拉函数肯定在这里是无法应用的，这里应用了容斥原理，
如上图为容斥原理的思路：
1.位运算遇到集合是奇数的就加，偶数的就减
2.队列数组
3.递归算法
分析：
n和1——a-1的不互素个数num1，互素个数a-1-num1
n和1——b的不互素个数num2，互素个数b-num2
最后结果为b-num2-(a-1-num1)
1.位运算：（素因子的个数全局变量cnt记录）
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long ll;
ll prime[100];
int cnt;
void init(int m)
{
cnt=0;
for(ll i=2;i*i<m;i++)
if(m%i==0){
prime[cnt++]=i;//prime储存素因子，cnt为素因子的个数
while(m%i==0){
m/=i;
}
}
if(m>1)
prime[cnt++]=m;//这里是因为有的n的因子大于sqrt(n)，比如14，他的素因子有2，7，
}
ll rong_chi(ll cur)
{
ll res,ans=0;
for(ll i=1;i<ll(1<<cnt);i++)
{
res=1;
ll flag=0;
for(ll j=0;j<cnt;j++)
{
if(i&(ll(1<<j))) //出现因子
{
flag++; //统计出现的集合个数
res*=prime[j]; //取并之后的因子乘积
}
}
if(flag&1)
ans+=cur/res; //奇数 加
else
ans-=cur/res; //偶数 减
}
return ans;
}
int main()
{
ll t;
cin>>t;
int icase=0;
while(t--){
memset(prime,0,sizeof(prime));
ll a,b,n;
int len=0;
cin>>a>>b>>n;
init(n);
printf("Case #%d: %lld\n",++icase,b-rong_chi(b)-(a-1-rong_chi(a-1)));
}
return 0;
}
2.队列数组（素因子个数用全局变量cnt记录）
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
int prime[50],cnt;
int sum[1<<11],q;
void init(int m)
{
cnt=0;
for(ll i=2;i*i<m;i++)
if(m%i==0){
prime[cnt++]=i;//prime储存素因子，cnt为素因子的个数
while(m%i==0){
m/=i;
}
}
if(m>1)
prime[cnt++]=m;//这里是因为有的n的因子大于sqrt(n)，比如14，他的素因子有2，7，
}
ll que[100005];
ll solve(ll m)
{
ll k,front=0,sum=0;
que[front++]=-1;
for(ll i=0;i<cnt;i++)//所有的素因子都加入队列
{
k=front; //记录上一次循环的所有因子的组合方式的个数
for(ll j=0; j<k;j++)//用这次的因子a[i]与前面的k中组合进行组合
que[front++]=que[j]*prime[i]*-1;// *（-1） 是因为容斥定理 “奇加偶减”性质
}
for(ll i=1;i<front;i++)//front为n的素因子的所有可能的组合方式，front=2^cnt-1，这里有效的把二进制位实现的所有种类个数从循环拿到队列中来了，所以这就适用于cnt的个数（也可以说n)较大的情况
sum+=m/que[i];
return sum; //sum为是n的因子的倍数的个数
}
int main()
{
int t,icase=0;
ll a,b,n;
scanf("%d",&t);
while(t--)
{
scanf("%lld%lld%lld",&a,&b,&n);
init(n);
printf("Case #%d: %lld\n",++icase,b-solve(b)-(a-1-solve(a-1)));
}
return 0;
}
3.递归（素因子的个数记录在全局变量cnt）
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
int prime[20],cnt;
void Init(int m)
{
int i;
cnt=0;
for(i=2;i*i<=m;i++)
if(m%i==0){
prime[cnt++]=i;
while(m%i==0) m/=i;
}
if(m!=1) prime[cnt++]=m;
}
ll Noprime(int m,ll n,int x)
{
ll i,ret=0;
for(i=x;i<cnt;i++)
ret+=n/prime[i]-Noprime(m,n/prime[i],i+1);
return ret;
}
int main()
{
int t,T,N;
ll A,B;
scanf("%d",&T);
for(t=1;t<=T;t++)
{
scanf("%lld%lld%d",&A,&B,&N); Init(N);
printf("Case #%d: %lld\n",t,B-Noprime(N,B,0)-(A-1-Noprime(N,A-1,0)));
}
return 0;
}