2016-09-22

Codeforces 665F Four Divisors【数论】

题目链接：

http://codeforces.com/contest/665/problem/F

题意：

给定$n(1 \le n \le 10^{11})$，求$[1,n]$中有多少个数含有四个因数。

分析：

一个数若除了$1$和本身外还有两个因数的情况只能是该数等于三个相同的质数或者两个不同的质数相乘。
三个相同的质数情况可以$n^{\frac{1}{3}}$枚举，也可以直接计算出来，但是要注意精度误差。
两个不同的质数情况可以枚举一个质数，然后计算出小于等于$\frac{n}{q}$大于$q$的质数个数，累加到答案中即可。
上述计算利用板子中$f,g$数组就可以解决。$其中f[i]表示\phi(n/i)，g[i]表示\phi(i)$。

代码：

/*************************************************************************
    > File Name: 665F.cpp
    > Author: jiangyuzhu
    > Mail: 834138558@qq.com 
    > Created Time: 2016/9/22 21:33:49
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 5;
const ll maxm = 1e11;
const ll maxp = sqrt(maxm) + 10;
ll f[maxp],g[maxp];
bool isprime[maxn];
int prime[maxn];
int tot = 0;
void init()
{
	for(int i = 2; i < maxn; i ++) isprime[i] = true;
	for(int i = 2; i < maxn; i++){
        if(isprime[i]) prime[tot++] = i;
        for(int j = 0; j < tot && i * prime[j] < maxn; j++){
            isprime[i * prime[j]] = false;
            if(i % prime[j] == 0) break;
        }
    }    
}
ll solve(ll n)
{
    ll i,j,m;
    for(m = 1; m * m <= n; m++) f[m] = n/m - 1;
    for(i = 1;i <= m; i++) g[i] = i-1;
    for(i = 2; i <= m; i++){
        if(g[i] == g[i-1]) continue;
        for(j = 1; j <= min(m - 1, n/i/i); j++){
            if(i * j < m) f[j] -= f[i * j] - g[i - 1];
            else f[j] -= g[n/i/j] - g[i-1];
        }
        for(j = m;j >= i * i; j--) g[j] -= g[j / i] - g[i - 1];
    }
	ll ans = 0;
    for(int i = 2; i < m; i++){
		if(g[i] == g[i - 1]) continue;
		ans += f[i] - g[i];
	}
	return ans;
}
int main (void)
{
	init();
	ll n;scanf("%I64d", &n);
	ll ans = 0;
	for(int i = 0; i < tot; i++){
		if(prime[i] * 1LL * prime[i] * prime[i] > n) break;
		ans++;
	}
	printf("%I64d\n", ans + solve(n));
	return 0;
}