Visible Trees

time limit per test 1 second memory limit per test 256 megabytes
There are many trees forming a m * n grid, the grid starts from (1,1). Farmer Sherlock is standing at (0,0) point. He wonders how many trees he can see.

If two trees and Sherlock are in one line, Farmer Sherlock can only see the tree nearest to him.

传送门:HDU2841

Input

The first line contains one integer t, represents the number of test cases. Then there are multiple test cases. For each test case there is one line containing two integers m and n(1 ≤ m, n ≤ 100000)

Output

For each test case output one line represents the number of trees Farmer Sherlock can see.

Sample Input

1
2
3
2
1 1
2 3

Sample Output

1
2
1
5

题解

经典题型 求1-n中与m互素的个数
这题就是求(1,1)到(m,n)中有几个(a,b)满足gcd(a,b)==1 即a,b互素
那么枚举i从1-m 求每个i与1-n中互素的个数
就是容斥原理的一套了
有篇博客写得很好:http://www.cnblogs.com/kane0526/archive/2013/03/14/2795446.html
有几个小细节 1是枚举每个数的素因数时如果最后n>1 别忘了加
2是数组实现容斥时要先放一个1进去 然后每次乘-1就对了

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
import java.io.*;  
import java.util.*;
public class Main {
static boolean prime[];
public static void main(String[] args) {
FastScanner sc=new FastScanner();
PrintWriter pw=new PrintWriter(System.out);
int n=sc.nextInt();
while(sc.hasNext()){
int a=sc.nextInt();
int b=sc.nextInt();
long res=0;
for(int i=1;i<=a;i++){
res+=cal(i,b);
}
pw.println(res);
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;
}
}