首页 > 代码库 > VIJOS 1889 天真的因数分解 ——莫比乌斯函数
VIJOS 1889 天真的因数分解 ——莫比乌斯函数
同理BZOJ2440
二分答案,不过这次变成了统计含有平方因子的个数
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define F(i,j,k) for (ll i=j;i<=k;++i) #define D(i,j,k) for (ll i=j;i>=k;--i) #define ll long long #define maxn 200005 int vis[maxn],mu[maxn],pr[maxn],top=0; void init() { F(i,2,maxn-1) { if (!vis[i]) mu[i]=1,pr[++top]=i; F(j,1,top) { if (i*pr[j]>=maxn) break; vis[i*pr[j]]=1; if (i%pr[j]==0) {mu[i*pr[j]]=0;break;} mu[i*pr[j]]=-mu[i]; } } } ll solve(ll n) { ll t=sqrt(n),ret=0; F(i,1,t) ret+=mu[i]*(n/(i*i)); return ret; } ll k,l,r; int main() { init(); scanf("%lld",&k); l=0;r=50000000000LL; while (l<r) { ll mid=l+r>>1; if (solve(mid)>=k) r=mid; else l=mid+1; } printf("%lld\n",r); }
VIJOS 1889 天真的因数分解 ——莫比乌斯函数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。