Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 5160 Solved: 2515
[Submit][Status][Discuss]
Description
小 X 自幼就很喜歡數。但奇怪的是,他十分討厭完全平方數。他覺得這些
數看起來很令人難受。由此,他也討厭所有是完全平方數的正整數倍的數。然而
這絲毫不影響他對其他數的熱愛。
這天是小X的生日,小 W 想送一個數給他作為生日禮物。當然他不能送一
個小X討厭的數。他列出了所有小X不討厭的數,然后選取了第 K個數送給了
小X。小X很開心地收下了。
然而現在小 W 卻記不起送給小X的是哪個數了。你能幫他一下嗎?
Input
包含多組測試數據。文件第一行有一個整數 T,表示測試
數據的組數。
第2 至第T+1 行每行有一個整數Ki,描述一組數據,含義如題目中所描述。
Output
含T 行,分別對每組數據作出回答。第 i 行輸出相應的
第Ki 個不是完全平方數的正整數倍的數。
Sample Input
4
1
13
100
1234567
Sample Output
1
19
163
2030745
HINT
對于 100%的數據有 1 ≤ Ki ≤ 10^9
, T ≤ 50
題解
一看到完全平方數的倍數,自然而然就想到莫比烏斯函數,又因為數據范圍較大
就想到二分來解決,所以先篩出莫比烏斯函數,之后根據容斥原理算出不是完全
平方數的倍數的個數。有些地方還是理解的不夠透徹。
代碼
#include<bits/stdc++.h>
#define LL long longusing namespace std;
const int MAXN = 1e5+5;int n,miu[MAXN],cnt,prime[MAXN],T;
bool vis[MAXN];inline LL check(LL x){int xx=(int)sqrt(x);LL ret=0;for(register int i=1;i<=xx;i++)ret+=miu[i]*(x/(i*i));return ret;
}signed main(){miu[1]=1;for(register int i=2;i<=MAXN;i++){if(!vis[i]) {vis[i]=1;prime[++cnt]=i;miu[i]=-1;}for(register int j=1;j<=cnt && (LL)prime[j]*i<=MAXN;j++){vis[(LL)i*prime[j]]=1;if(i%prime[j]==0){miu[(LL)i*prime[j]]=0;break;}else miu[(LL)i*prime[j]]=-miu[i];}}scanf("%d",&T);while(T--){scanf("%d",&n);LL l=0,r=n*2;while(l<r){LL mid=(l+r)>>1;if(check(mid)<n) l=mid+1;else r=mid;}printf("%lld\n",r);}return 0;
}