UESTC 618 无平方因子数 (容斥＋莫比乌斯反演)

分类：

无平方因子数

Time Limit: 4000/2000MS (Java/Others)

Memory Limit: 65535/65535KB (Java/Others)

Submit Status无平方因子数即对于任意一个素数p，p2都不会整除那个数，如1 , 5=5 , 15=3×5都是无平方因子数，而20=22×5不是。现在给定一个n (1≤n<1012) ，求区间[1,n]中无平方因子数的个数。Input第一行有个整数T，代表数据组数（T≤10）接下来有T行，每行有个整数n (1≤n<1012)Output输出T行，，每行输出一个整数代表区间[1,n]内的无平方因子数的个数。Sample Input 3110

Sample Output

Source

UESTC Training for Math

题目链接：

题目分析：又是无平方因子数，比BZOJ那题简单很多，直接算就行了，参照BZOJ 2440

#include <cstdio>#include <cstring>#include <algorithm>#define ll long longusing namespace std;int const MAX = 1e6 + 5;int mob[MAX], p[MAX];bool prime[MAX];void Mobius(){int pnum = 0;memset(prime, true, sizeof(prime));mob[1] = 1;for(int i = 2; i < MAX; i++){if(prime[i]){p[pnum ++] = i;mob[i] = -1;}for(int j = 0; j < pnum && i * p[j] < MAX; j++){prime[i * p[j]] = false;if(i % p[j] == 0){mob[i * p[j]] = 0;break;}mob[i * p[j]] = -mob[i];}}}ll cal(ll n){ll cnt = 0;for(ll i = 1; i * i <= n; i++)cnt += (ll) mob[i] * (n / (i * i));return cnt;}int main(){Mobius();int T;scanf("%d", &T);while(T –){ll n;scanf("%lld", &n);printf("%lld\n", cal(n));}}

上一篇BZOJ 2440 完全平方数 (容斥＋莫比乌斯反演＋二分)

顶0踩0

微笑的去寻找一个不可能出现的你。

相关文章：

你感兴趣的文章：

标签云：