程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu 4135 Co-prime(容斥原理)

hdu 4135 Co-prime(容斥原理)

編輯：C++入門知識

hdu 4135 Co-prime(容斥原理)

求連續區間[a,b]內與n互質的數的個數。

因為a,b相當大，考慮用容斥原理。只需先求出[a,b]內與n不互質的數的個數，等於[1,b]內與n不互質的個數 - [1,a-1]內與n不互質的個數。問題轉化為求【1，m】內與n不互質的數的個數。

先對n分解質因子，[1,m]內是n的質因子的倍數的那些數肯定與n不互質，但是有許多重復的，需要減去。質因子解法有多種，隊列數組或狀態壓縮。

例如30的質因子是2,3,5，[1,m]內與30互質的數的個數表示為 n/2 + n/3 + n/5 - n/(2*3) - n/(2*5) - n/(3*5) + n/(2*3*5)。發現質因子個數是奇數的做加法，是偶數的做減法。隊列數組解法為模擬一個隊列，初始將1加入隊列，之後每次取出n的一個質因子依次與隊列中的數相乘後置於隊尾，每次乘-1決定其前面的正負號。最後隊列裡的就是上式所有的分子，然後解之。狀態壓縮便是將取出的質因子置為1沒取出的置為0，得到一個數res，若res的質因子個數是奇數就加上，是偶數就減，求和就是與m不互素的數的個數，解之。

#include 
#include 
#include
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define LL __int64
//#define LL long long
#define eps 1e-9
#define PI acos(-1.0)
using namespace std;
const LL INF = 1<<30;
const int maxn = 100010;

LL a,b,n;
LL ans;
int fac[maxn];
int prime[maxn];
int facCnt;

void getPrime()
{
	bool flag[maxn];
	memset(flag,false,sizeof(flag));
	prime[0] = 0;

	for(int i = 2; i < maxn; i++)
	{
		if(flag[i] == false)
			prime[++prime[0]] = i;
		for(int j = 1; j <= prime[0]&&i*prime[j] 1)
		fac[facCnt++] = tmp;
}

LL solve(LL m)
{
	//位運算
	LL anw = 0;
	for(int i = 1; i < (1< 
 
#include 
#include 
#include
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define LL __int64
//#define LL long long
#define eps 1e-9
#define PI acos(-1.0)
using namespace std;
const LL INF = 1<<30;
const int maxn = 100010;

LL a,b,n;
LL ans;
int fac[maxn];
int prime[maxn];
int facCnt;

void getPrime()
{
	bool flag[maxn];
	memset(flag,false,sizeof(flag));
	prime[0] = 0;

	for(int i = 2; i < maxn; i++)
	{
		if(flag[i] == false)
			prime[++prime[0]] = i;
		for(int j = 1; j <= prime[0]&&i*prime[j] 1)
		fac[facCnt++] = tmp;
}

LL solve(LL m)
{
	//隊列數組
	int que[110];
	int l = 0;
	que[l++] = 1;

	for(int i = 0; i < facCnt; i++)
	{
		int k = l;
		for(int j = 0; j < k; j++)
			que[l++] = fac[i]*que[j]*(-1);
	}

	LL anw = 0;
	for(int i = 0; i < l; i++)
		anw += m/que[i];
	return anw;
}

int main()
{
	int test;
	scanf(%d,&test);
	getPrime();
	for(int item = 1; item <= test; item++)
	{
		scanf(%I64d %I64d %I64d,&a,&b,&n);
		getFac();
		ans = solve(b) - solve(a-1);
		printf(Case #%d: %I64d
,item,ans);
	}
	return 0;
}