HDU 4135 Co-prime (容斥原理)

HDU 4135 Co-prime (容斥原理)

題目戳這裡

題意：求一個區間[a,b]中有多少個與n互素的數。

思路：

這道題是容斥原理的模板題之一，容斥原理請參考容斥原理詳述，很好的一篇文章。

[a,b]中與n互素的數目可轉化為[1,b]-[1,a-1]的數目。

給出整數n和r。求區間[1;r]中與n互素的數的個數的方法：

解決它的逆問題，求不與n互素的數的個數。

考慮n的所有素因子pi(i=1…k)

在[1;r]中有多少數能被pi整除呢？它就是：

然而，如果我們單純將所有結果相加，會得到錯誤答案。有些數可能被統計多次（被好幾個素因子整除）。所以，我們要運用容斥原理來解決。

我們可以用o(2^k)的算法求出所有的pi組合，然後計算每種組合的pi乘積，通過容斥原理來對結果進行加減處理。

code：

/*
*Author : Flint_x 
*Created Time : 2015-07-20 13:22:56 
*File name : whust1_H.cpp 
*/

#include
#include
#include
#include
#include
#include
#include
#include
#include