Problem Description

小 X 自幼就很喜歡數(shù)。但奇怪的是，他十分討厭完全平方數(shù)。他覺得這些數(shù)看起來很令人難受。由此，他也討厭所有是完全平方數(shù)的正整數(shù)倍的數(shù)。然而這絲毫不影響他對其他數(shù)的熱愛。?

這天是小X的生日，小 W 想送一個(gè)數(shù)給他作為生日禮物。當(dāng)然他不能送一個(gè)小X討厭的數(shù)。他列出了所有小X不討厭的數(shù)，然后選取了第 K個(gè)數(shù)送給了小X。小X很開心地收下了。

然而現(xiàn)在小 W 卻記不起送給小X的是哪個(gè)數(shù)了。你能幫他一下嗎？

Input

包含多組測試數(shù)據(jù)。文件第一行有一個(gè)整數(shù) T，表示測試數(shù)據(jù)的組數(shù)。?

第2 至第T+1 行每行有一個(gè)整數(shù)Ki，描述一組數(shù)據(jù)，含義如題目中所描述。?

對于 100%的數(shù)據(jù)有 1 ≤ Ki ≤ 10^9, ? ?T ≤ 50

Output

含T 行，分別對每組數(shù)據(jù)作出回答。第 i 行輸出相應(yīng)的第Ki 個(gè)不是完全平方數(shù)的正整數(shù)倍的數(shù)。

Examples

Input

4?
1?
13?
100?
1234567?

Output

1?
19?
163?
2030745?

思路：

簡單來說，題目是給出 t 組查詢，每組給出一個(gè) k，查找第 k 個(gè)不含完全平方因子的數(shù)

因此，直接考慮二分答案，計(jì)算第 k 個(gè)不含完全平方因子的數(shù)

對于區(qū)間 [1,n] 上的無完全平方因子數(shù)的個(gè)數(shù)，考慮 sqrt(n) 內(nèi)的整數(shù) a，由于含有平方因子的數(shù)需要排除，因此需要減去每個(gè)質(zhì)數(shù)的平方的倍數(shù)的個(gè)數(shù)，但這樣會使得減去的個(gè)數(shù)過多，例如 36 既被 4 減又被 9 減，因此需要再加上由質(zhì)數(shù)乘積的平方的數(shù)的數(shù)，可以發(fā)現(xiàn)，這個(gè)過程是一個(gè)容斥的過程

然而問題在于，無法確定一個(gè)乘積平方的數(shù)是加還是減，但觀察式子可以發(fā)現(xiàn)，一個(gè)數(shù)的乘積 x 的前面的系數(shù)就是 u(x)

那么，對于 n，n?以內(nèi)的 a 的平方數(shù)的倍數(shù)有 n/(a^2) 個(gè)，因此，對于從 1 到 sqrt(n) 的所有整數(shù) i，最終的結(jié)果就是 n/(i^2)*mu[i]

Source Program

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #include<bitset> #define PI acos(-1.0) #define INF 0x3f3f3f3f #define LL long long #define Pair pair<int,int> LL quickPow(LL a,LL b){ LL res=1; while(b){if(b&1)res*=a; a*=a; b>>=1;} return res; } LL quickModPow(LL a,LL b,LL mod){ LL res=1; a=a%mod; while(b){if(b&1)res=(a*res)%mod; a=(a*a)%mod; b>>=1;} return res; } LL getInv(LL a,LL mod){ return quickModPow(a,mod-2,mod); } const double EPS = 1E-10; const int MOD = 1E9+7; const int N = 100000+5; const int dx[] = {-1,1,0,0,-1,-1,1,1}; const int dy[] = {0,0,-1,1,-1,1,-1,1}; using namespace std;int mu[N]; int prime[N]; bool bprime[N]; int cnt; void getMu(int n){//線性篩求莫比烏斯函數(shù)cnt=0;mu[1]=1;//根據(jù)定義，μ(1)=1memset(bprime,false,sizeof(bprime));for(int i=2;i<=n;i++){//求2~n的莫比烏斯函數(shù)if(!bprime[i]){prime[++cnt]=i;//存儲質(zhì)數(shù)mu[i]=-1;//i為質(zhì)數(shù)時(shí)，μ(1)=-1}for(int j=1;j<=cnt&&i*prime[j]<=n;j++){//枚舉i之前的素?cái)?shù)個(gè)數(shù)bprime[i*prime[j]]=true;//不是質(zhì)數(shù)if(i%prime[j])//i不是prime[j]的整數(shù)倍時(shí)，i*prime[j]就不會包含相同質(zhì)因子mu[i*prime[j]]=-mu[i];//mu[k]=mu[i]*mu[prime[j]]，因?yàn)閜rime[j]是質(zhì)數(shù)，mu值為-1else{mu[i*prime[j]]=0;break;//留到后面再篩}}} } LL cal(LL n){LL res=0;for(LL i=1;i*i<=n;i++)res+=(n/(i*i)*mu[i]);return res; } int main(){getMu(100000);int t;scanf("%d",&t);while(t--){LL k;scanf("%lld",&k);LL res=0;LL left=k,right=1E10;while(left<=right){LL mid=(left+right)/2;if(cal(mid)<k)left=mid+1;else {res=mid;right=mid-1;}}printf("%lld\n",res);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的完全平方数（HYSBZ-2440）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。