题目链接
Time limit 10000 ms Memory limit 31072 kB
Problem 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
题意:
求n，m之间有多少对数满足gcd(i, j) 不是一个完全平方数。
思路:
用莫比乌斯反演来做容斥
对于一个数n我们考虑如何计算n以内有多少个不是完全平方数的倍数的数，
ans = n - 一个质数的平方数的倍数 + 两个质数的平方数的倍数…
那么其实那个神秘的容斥系数就是莫比乌斯反演的系数。
那么这个题最后就是我们二分答案，然后用那个反演check一下。
代码:
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
|
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<string>
using namespace std;
typedef long long LL;
const double eps = 1e-8;
const double C = 0.57721566490153286060651209;
const double pi = acos(-1.0);
const int mod = 1e9 + 7;
const int maxn = 1e5 + 10;
int pri[maxn], mu[maxn];
bool vis[maxn];
void Mobius(){
int cnt = 0;
mu[1] = 1;
for(int i = 2; i < maxn; ++i){
if(!vis[i]){
pri[++cnt] = i;
mu[i] = -1;
}
for(int j = 1; j <= cnt && i * pri[j] < maxn; ++j){
vis[i*pri[j]] = true;
if(i % pri[j] == 0){
mu[i*pri[j]] = 0;
break;
}mu[i*pri[j]] = - mu[i];
}
}
}
bool check(int n, int k){
int ans = 0;
for(int i = 1; i * i <= n; ++i)
ans += n / (i*i) * mu[i];
return ans >= k;
}
int main(){
int t;
Mobius();
scanf("%d", &t);
while(t--){
int n;
scanf("%d", &n);
int l = 1, r = n << 1, ans;
while(l <= r){
int mid = (r - l) / 2 + l;
if(check(mid, n)) r = mid - 1, ans = mid;
else l = mid + 1;
}printf("%d\n", ans);
}
return 0;
}
|