刚开始不知道用二分，因为没有发现序列单调不下降的性质；
留意二分查找需找到下界。
二分查找起点的右边界取m*n是不够的，实际查找到的结果可能远大于该值。
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
70
71
72
73
74
75
76
77
|
import java.io.*;
import java.util.*;
public class Main {
static Vector<Integer> v1=new Vector<Integer>();
static Vector<Integer> v2=new Vector<Integer>();
static HashSet<Integer> st=new HashSet<Integer>();
static Integer[] fac=new Integer[0];
static Vector<Integer> get_prime_factor(int n){
Vector<Integer> res=new Vector<Integer>();
res.clear();
for(int i=2;i*i<=n;i++)
if (n%i==0){
res.add(i);
while(n%i==0)
n/=i;
}
if (n>1) res.add(n);
return res;
}
static long check(long n){
long res=0L;
int m=fac.length;
for(int i=1;i<(1L<<m);i++){
long tmp=1L;
boolean tag=false;
for(int j=0;j<m;j++)
if (((1L<<j)&i)>0L){
tmp*=fac[j].longValue();
tag^=true;
}
res+=tag?n/tmp:-n/tmp;
}
return n-res;
}
static long bisearch(long low,long high,long key){
long l=low,r=high,mid;
while(l<r){
mid=(l+r)>>1;
if (check(mid)>=key)
r=mid;
else
l=mid+1;
}
return l;
}
public static void main(String[] args) throws IOException{
InputReader in=new InputReader(System.in);
PrintWriter out=new PrintWriter(System.out);
int T=in.nextInt(),cas=0;
while(T-->0){
int m=in.nextInt();
int n=in.nextInt();
int k=in.nextInt();
v1=get_prime_factor(m);
v2=get_prime_factor(n);
st.clear();
for(Integer e:v1.toArray(new Integer[0]))
st.add(e);
for(Integer e:v2.toArray(new Integer[0]))
st.add(e);
fac=st.toArray(new Integer[0]);
out.println("Case "+(++cas)+": "+bisearch(1, 0x3f3f3f3f3f3f3f3fL, k));
}
out.flush();
out.close();
}
}
|
较为神奇的是，把以上代码的check()函数（实现容斥原理的计算）替换为以下实现后，效率大有提升。
1
2
3
4
5
6
| static long check(long n,int low){
long sum=0L;
for(int i=low;i<fac.length;i++)
sum+=n/fac[i].longValue()-check(n/fac[i].longValue(),i+1);
return sum;
}
|