PRoblem

acm.timus.ru/problem.aspx?space=1&num=2070

題意

條件1：質數

條件2：不一定是質數，但因子個數（包括1和本身）是質數的數

求 [ L , R ] 內同時滿足或同時不滿足兩個條件的數的個數。

Analysis

先求反面：只滿足其中一個條件的數的個數，然后用總數去減。

因為質數的因子個數一定是質數 2，所以反面的數就是：因子個數是質數的合數。

這樣的數一定是某一個質數的某次冪（除去1次冪，因為不算質數），而且指數滿足：指數+1 是一個質數。

因為將一個數進行質數分解，如果有多個質因子的冪（非0次冪），則這個數的因子數一定不是質數。舉個例子，a = b^c * d^e，那么由排列組合 a 的因子個數就是：n = (c + 1) * (e + 1)個，而 n 一定不是質數，因為它至少可以拆成：(c + 1) * (e + 1)。所以一定是某一個質數的某次冪。

假如某個數 a 可以素數分解成： a = b^c，那 a 的因子個數就是 c+1 個（1，b，b^2，…，b^c），所以要求的質數冪還要其指數滿足：指數+1 是質數。

可以分別算 [ 2，R ] 和 [ 2，L-1 ] 的反面的數的個數然后再相減得出 [ L，R ] 內反面的數個數。

先打個 [ 1，1e6 ] 的質數表，升序枚舉質數的在范圍內的冪來統計。

Source code

#include <cstdio>#include <cstring>using namespace std;const int LEN = 1000000;int p[78498], top;bool num[LEN+1];void sieve(){	top = 0;	memset(num, true, sizeof num);	for(int i=2; i<=LEN; ++i)		if(num[i])		{			p[top++] = i;			for(int j=i<<1; j<=LEN; j+=i)				num[j] = false;		}}int solve(long long n){	int cnt = 0;	// 從2次冪開始	for(int i=0, zhishu=2; i<top && p[i]<=n; ++i, zhishu=2)		for(long long j=(long long)p[i]*p[i]; j<=n; j*=p[i], ++zhishu)			if(num[zhishu+1])				++cnt;	return cnt;}int main(){	sieve();	long long l, r;	scanf("%I64d%I64d", &l, &r);	printf("%I64d/n", (r-l+1) - (solve(r)-solve(l-1)) );	return 0;}