题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2440
题意：求第 k 个无平方因子数
首先直接求这个数是什么不是很容易... 考虑二分答案，问题转化为求 1-n 有多少个无平方因子数
这也是不好求的 但是我们知道 1-n 中有\(\frac{n}{i}\) 个数含有某因子 i 有重复 于是容斥
直接容斥的话是指数级别的 我们考虑对于因子 4 如果处理过 4 显然不需要处理 16
所以处理质因子即可
分别处理出现一个质因子、两个质因子、三个质因子... 的情况，发现容斥时的正负性恰好为\(\mu_i\)
（这是显然的... 由\(\mu_i\) 的定义得）
于是就结束了 二分复杂度\(log_k\)，判断过程\(\sqrt k\) ，总复杂度\(O(log_k\sqrt k)\)
|
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 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <iomanip> #include <cmath> #define ll long long #define N 50000 using namespace std; int pri[N+10],n,mu[N+10],cnt; bool pd[N+10]; int T,k; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } void get_mu() { mu[1]=1; for(int i=2;i<=N;i++) { if(!pd[i]) { pri[++cnt]=i; mu[i]=-1; } for(int j=1;i*pri[j]<=N&&j<=cnt;j++) { pd[i*pri[j]]=1; if(i%pri[j]==0) { mu[i*pri[j]]=0; break; } mu[i*pri[j]]=-mu[i]; } } } bool check(int x) { int tot=0; for(int i=1;i*i<=x;i++) { tot+=mu[i]*(x/(i*i)); } if(tot>=k)return 1; return 0; } int solve(ll x) { ll l=1,r=x<<1,ans=0; while(l<=r) { ll mid=(l+r)>>1; if(check(mid))ans=mid,r=mid-1; else l=mid+1; } return ans; } int main() { T=read(); get_mu(); while(T--) { k=read(); printf("%d\n",solve(k)); } } |
Comments | NOTHING