程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> SDUT 3023-當N遇上M（容斥原理）

SDUT 3023-當N遇上M（容斥原理）

編輯：C++入門知識

SDUT 3023-當N遇上M（容斥原理）

題目鏈接：傳送門

題意：求[1,n]內與m互質的個數。

容斥原理：奇加偶減（奇數個類的計數和-偶數個類的計數和）

對於這個問題，首先求出m的質因數fac[] , 然後所在區間內有n/fac[i]個數一定不能與m互質（比如m=8，n=10，對於fac[]=2,有2,4,6,8,10 即5（10/2）個數不能與8互質）。。枚舉每一個質因數選還是不選。可以位運算，也可以dfs

第一發容斥，准備系統的刷一下容斥的專題了。。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define maxn 360
#define _ll __int64
#define ll long long
#define INF 0x3f3f3f3f
#define Mod 1000000007
#define pp pair
#define ull unsigned long long
#define max(x,y) ( ((x) > (y)) ? (x) : (y) )
#define min(x,y) ( ((x) > (y)) ? (y) : (x) )
using namespace std;
ll fac[1111],tot,ans;
void div(ll x)//分解質因數
{
	tot=0;
	for(ll i=2;i*i<=x;i++)
	{
		if(x&&x%i==0)
		{
			fac[tot++]=i;
			while(x&&x%i==0)
				x/=i;
		}
	}
	if(x>1)
		fac[tot++]=x;
}
void dfs(ll num,ll s,ll r,ll n)//n為范圍 即（1,n）
{
	if(num==tot)
	{
		if(s&1)ans-=n/r;//容斥原理：奇加偶減(那這裡為什麼還是減？因為n/r是不能和m互質的個數啦)
		else ans+=n/r;
		return ;
	}
	dfs(num+1,s,r,n);
	dfs(num+1,s+1,r*fac[num],n);
}
int main()
{
	ll n,m;
	while(~scanf("%lld%lld",&n,&m))
	{
		ans=0;div(m);
		dfs(0,0,1,n);
		printf("%lld\n",ans);
	}
	return 0;
}

C++入門知識

C++的頭文件和實現文件分別寫什麼，頭文件怎麼寫

C++的頭文件和實現文件分別寫什麼，頭文件怎麼寫原文：htt

C++指針筆記，指針筆記

C++指針筆記，指針筆記什麼是指針：指針是一個特殊的變量，

希爾排序

希爾排序（摘自wiki）一個更好理解的希爾排序實現

C++中的 pure virtual function call

前幾天我們項目剛剛解決了一個pure virtual

C語言基於GTK+Libvlc實現的簡易視頻播放器，gtklibvlc

C語言基於GTK+Libvlc實現的簡易視頻播放器，gtkl

用C++實現多線程Mutex鎖

本文目的：用C++