「SPOJ 4168」SQFREE - Square-free integers

发表于 | | 阅读次数:
字数统计: 396 字

Description

题目链接：SPOJ 4168

求 $n$ 以内有多少个数不能被任何一个完全平方数（除 $1$ 以外）整除。

本题 $T$ 组数据。

数据范围：$1\le T\le 100$，$1\le n\le 10^{14}$

Solution

这个问题直接考虑无从下手，因此我们可以从反面考虑：求有多少个数是完全平方数的倍数。

枚举 $i$（$2\le i\le \sqrt n$），那么对于答案的贡献为 $\dfrac{n}{i^2}$，但是这样会重复计算：如 $36$ 在 $i=2,3$ 时都会被计算到，所以需要容斥。

我们强制这里的 $i$ 没有重复质因子，这样一来虽然会算重复，但是不会遗漏。如果 $i$ 的质因子个数为奇数，那么对答案为正的贡献，否则为负的贡献。可以证明这个容斥是正确的。

时间复杂度：$O(T\sqrt n)$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
 
#include <cstdio>

const int N=1e7+5;
int tot,p[N/10],f[N];
bool flg[N];

void init() {
    for(int i=2;i<N;++i) {
        if(!flg[i]) p[++tot]=i;
        for(int j=1;j<=tot&&i*p[j]<N;++j) {
            flg[i*p[j]]=1;
            if(i%p[j]==0) break;
        }
    }
}
void dfs(int st,int sum,int cnt) {
    f[sum]=cnt&1?1:-1;
    for(int i=st;i<=tot;++i) {
        long long now=1LL*sum*p[i];
        if(now>N) break;
        dfs(i+1,now,cnt+1);
    }
}
int main() {
    init();
    dfs(1,1,0);
    int T;
    for(scanf("%d",&T);T--;) {
        long long n;
        scanf("%lld",&n);
        long long ans=0;
        for(int i=2;1LL*i*i<=n;++i) if(f[i]) ans+=f[i]*n/(1LL*i*i);
        printf("%lld\n",n-ans);
    }
    return 0;
}
0%