首页 > 代码库 > bzoj 2440 完全平方数
bzoj 2440 完全平方数
这是一道论文题。
题意：选出第k个无平方因子的数。
思路：二分答案。
某一个区间的无平方因子的数的个数怎么求呢？ 可以筛。
这里可以莫比乌斯。
首先什么是莫比乌斯函数呢？
回到本题：
他是一个莫比乌斯函数的应用。
对于1~ mid 中，不含平方因子的个数为：
n - sum(i^2) 其中 i 为素数。
含不含平方因子：就是将 N 质因数分解，只有u(n) != 0的值才是不含质因数因子的。但是开不来10^9的数组，来遍历u(n)，用素数优化。
例如： 4，9，4n，9n，这些数得删掉，4的倍数的个数 为 n/4 n/9,
所谓平方因子也是 一些素数的平方得到的。
那么这里就有一个容斥定理，n - 每个质数的平方因子的数的倍数，（这里不用算素数，因为有莫比乌斯函数做系数）+每两个质数的乘积的平方因子的数的倍数-每三个... ...
例如：删掉了4的倍数，9的倍数，那么36就被删了两次，（容斥定理）
#include <bits/stdc++.h>using namespace std;const int n = 1e+5;typedef long long ll;int mu[n];void getMu() { for(int i=1;i<=n;i++) { int target = i == 1? 1: 0; int delta = target - mu[i]; mu[i] = delta; for(int j=i+i;j<=n;j+=i) mu[j] +=delta; }}ll k;ll calc(ll mid) { ll sq = sqrt(mid); ll ans = 0; for(ll i=1;i<=sq;++i) { ans+=mu[i]*(mid/(i*i)); } return ans;}int main(int argc, char const *argv[]){ getMu(); ll t; scanf("%I64d",&t); for(ll z=0;z<t;++z) { scanf("%I64d",&k); ll l = 0,r = k*2; while(l<r) { ll mid = (l+r)/2; if(calc(mid)>=k) r = mid; else l = mid + 1; } cout<<l<<endl; } return 0;}
bzoj 2440 完全平方数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。