• 微信公众号：美女很有趣。 工作之余，放松一下，关注即送10G+美女照片！

# P4318 完全平方数

1周前 (06-08) 11次浏览

[Ans=n-F(A)+F(B)-F(C)cdots
]

``````#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long LL;
const LL INF = 0x7fffffff;
const int N = 1e6 + 10;
int T, n, tot, mu[N], prm[N];
bool vis[N];

int read(){
int x = 0, f = 1; char c = getchar();
while(c < '0' || c > '9') f = (c == '-') ? -1 : 1, c = getchar();
while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
return x * f;
}

void Get_Mu(){
mu[1] = 1;
for(int i = 2; i <= N - 10; i ++){
if(!vis[i])
prm[++ tot] = i, mu[i] = -1;
for(int j = 1, num; j <= tot && (num = prm[j] * i) <= N - 10; j ++){
vis[num] = true;
if(i % prm[j]) mu[num] = - mu[i];
else{
mu[num] = 0;
break;
}
}
}
}

bool chck(LL mid){
LL sum = 0;
for(int i = 1; i * i <= mid; i ++)
sum += 1LL * mu[i] * (mid / (i * i));
return sum >= n;
}

int main(){
Get_Mu();
T = read();
while(T --){
n = read();
LL l = 1, r = INF;
while(l < r){
LL mid = (l + r) >> 1;
if(chck(mid)) r = mid;
else l = mid + 1;
}
printf("%lldn", l);
}
return 0;
}
``````