GCD
time limit per test 2.5 second memory limit per test 256 megabytes
Given 5 integers: a, b, c, d, k, you’re to find x in a…b, y in c…d that GCD(x, y) = k. GCD(x, y) means the greatest common divisor of x and y. Since the number of choices may be very large, you’re only required to output the total number of different number pairs.
Please notice that, (x=5, y=7) and (x=7, y=5) are considered to be the same.

You can assume that a = c = 1 in all test cases.

传送门:HDU1695

Input

The input consists of several test cases. The first line of the input is the number of the cases. There are no more than 3,000 cases. Each case contains five integers: a, b, c, d, k, 0 < a <= b <= 100,000, 0 < c <= d <= 100,000, 0 <= k <= 100,000, as described above.

Output

For each test case, print the number of choices. Use the format in the example.

Sample Input

1
2
3
2
1 3 1 5 1
1 11014 1 14409 9

Sample Output

1
2
Case 1: 9
Case 2: 736427

题解

题意:求 1-b 和 1-d中 gcd(i,j)=k 的对数 且(x,y)=(y,x) 转化一下 变成求 1-b/k 和 1-d/k 中gcd(i,j)=1的对数 我分别用容斥和莫比乌斯写了下 容斥2000ms 莫比乌斯200ms 都要注意特判k=0的情况 容斥的话还要考虑重复的问题 枚举i:1-min(b,d) j:1-max(b,d) 枚举j时j>=i(保持有序性)即求 i与i到j互素中的对数 这样不会重复算 莫比乌斯则是神奇的操作 http://www.cnblogs.com/pdev/p/4098914.html 看这篇博客学习的
## AC code:(不包含输入类)
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
/*容斥*/
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) {
FastScanner sc=new FastScanner();
PrintWriter pw=new PrintWriter(System.out);
int t=sc.nextInt();
int q=0;
while(sc.hasNext()){
q++;
pw.print("Case "+q+": ");
int a=sc.nextInt();
int b=sc.nextInt();
int c=sc.nextInt();
int d=sc.nextInt();
int k=sc.nextInt();
long count1=0;
int min=Math.min(b, d);
int max=Math.max(b, d);
if(k==0){
pw.println(0);
}else{
for(int i=1;i<=min/k;i++){
count1+=cal(i,max/k)-cal(i,i-1); //保证不重复的对数
}
pw.println(count1);
}
pw.flush();
}

}
//jisuan 1~b zhongyu a huzhidegeshu
static long cal(int a,int b){
ArrayList<Integer>queue=new ArrayList<Integer>();
ArrayList<Integer>list=fenjie(a);
queue.add(1);
for(int i=0;i<list.size();i++){
int k=queue.size();
for(int j=0;j<k;j++){
queue.add(list.get(i)*queue.get(j)*(-1));
}
}
long sum=0;
for(int i=0;i<queue.size();i++){
sum+=b/queue.get(i);
}
return sum;
}
static ArrayList<Integer> fenjie(int n){
ArrayList<Integer>list=new ArrayList<Integer>();
for(int i=2;i<=Math.sqrt(n);i++){
if(n%i==0){
list.add(i);
while(n%i==0){
n/=i;
}
}
}
if(n>1)list.add(n); //important
return list;
}
}

/*莫比乌斯*/
import java.io.*;
import java.util.*;
public class Main {
static int[]prime=new int[100050];
static boolean[]notp=new boolean[100050];
static int[]mu=new int[100050];
public static void main(String[] args) {
FastScanner sc=new FastScanner();
PrintWriter pw=new PrintWriter(System.out);
int t=sc.nextInt();
int q=0;
makeMobius();
while(sc.hasNext()){
q++;
pw.print("Case "+q+": ");
int a=sc.nextInt();
int b=sc.nextInt();
int c=sc.nextInt();
int d=sc.nextInt();
int k=sc.nextInt();
if(k==0)pw.println(0);
else{
long min=Math.min(b, d)/k;
long max=Math.max(b, d)/k;
long count1=0;
long count2=0;
for(int i=1;i<=min;i++){
count1+=mu[i]*(min/i)*(min/i); //1-min算了两遍
}
for(int i=1;i<=min;i++){
count2+=mu[i]*(min/i)*(max/i);
}
pw.println(count2-count1/2);
}
pw.flush();
}

}
static void makeMobius() {
Arrays.fill(notp, false);
mu[1] = 1;
int pnum=0;
for (int i = 2; i < 100010; i++) {
if (!notp[i]) {
prime[++pnum] = i; mu[i] = -1;
}
for (int j = 1; prime[j]*i < 100010; j++) {
notp[prime[j]*i] = true;
if (i%prime[j] == 0) {
mu[prime[j]*i] = 0;
break;
}
mu[prime[j]*i] = -mu[i];
}
}
}
}