程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> HDU 4135 Co

HDU 4135 Co

編輯：關於C++

題目戳這裡

題意：求一個區間[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整除呢？它就是：

height=47

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

我們可以用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
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const double eps(1e-8);
typedef long long lint;

#define cls(a) memset(a,0,sizeof(a))
#define rise(i,a,b) for(int i = a ; i <= b ; i++)
#define fall(i,a,b) for(int i = a ; i >= b ; i--)

vector p;
lint solve (lint n, lint r) {
        p.clear();
        for (lint i=2; i*i<=n; ++i)
               if (n % i == 0) {
                       p.push_back (i);
                       while (n % i == 0)
                               n /= i;
               }
        if (n > 1)
               p.push_back (n);
        lint sum = 0;
        for (lint msk=1; msk<(1<> T;
	rise(kase,1,T){
		lint a,b,n;
		cin >> a >> b >> n;
		lint ans = solve(n,b) - solve(n,a-1);
		cout << Case # << kase << :  << ans << endl;
		
		
	}
    return 0;
}