第一题就是求给定n，在小于n的数中，有多少个互质数对。基本上可以递推得到，val[n+1]=val[n]+phi(n)，phi的功能就是得到小于n的且与n互质的数的个数。generate_primes（）生成这样的一个数列comp，其中comp[i]为数i的最小质因子，比如comp[4]=2,comp[5]=5,comp[9]=3....。
具体讲一下phi的原理：计算小于n的且与n互质的数的个数，采取了排除的方法。我们知道对于任何一个数都可以表示成n=a1*a1....a2*a2...an*an..也就是若干的质数的积，且1<a1<a2<a3...<an。那我们要做的就是排除掉小于等于n的数中有因子a1,a2,...an的数的个数就行了。现在我们希望快速知道对于任意一个数他的a1是多少，这就是comp[]的作用。如果知道了a1那么就可以得到小于等于n的且与n有公共因子的数的个数为n/a1,那么与n互质的就有res=(n-n/a1)个。接下来对于函有a2因子的数有n/a2个，但要加上n/(a1*a2)个，因为对于他们的公倍数显然排除了两次，这样与n互质的就有res-n/a2+n/(a1*a2)=res-(n-n/a1)/a2=res-res/a2。对于a3则是res=res-res/a3。于是有如下的关系
1  res=n
2  res=res-res/ai
直到处理完所有的ai
[code=c]
#include <cstdio>



#define MAXPRIME 1000001 
int comp[MAXPRIME];

void generate_primes() { //生成1-1000000的最小质因子
    int i;
    comp[0] = comp[1] = 1;
    for (i=2; i<MAXPRIME; i+=2)
        comp[i] = 2;
    for (i=3; i<=(MAXPRIME-1)/i; i+=2) {
        if (!comp[i]) {
                        comp[i] = i;
            for (int j=i*i; j<MAXPRIME; j+=i+i)
                comp[j] = i;
        }
    }
        for (; i < MAXPRIME; i += 2)
                if (!comp[i])
                        comp[i] = i;
}

int phi(int n) {  //得到小于n的且与n互质的个数
        int res = n;//n的作用仅仅为了取得不同的因子
        while (n > 1)
        {
                int f = comp[n];
                res /= f;//=>等同于(res-res/f)
                res *= f-1;//
                while (n % f == 0)//去掉已经处理了的因子，也就是把相同的ai都除掉
                        n /= f;
        }
    return res;
}

long long val[MAXPRIME];

int main()
{
        generate_primes();
        for (int i = 2; i < MAXPRIME; i++)//递推
                val[i] = val[i-1] + phi(i);

        int kases;
        for (scanf("%d", &kases); kases; kases--)
        {
                int x;
                scanf("%d", &x);
                printf("%I64ld\n", 2*val[x] + 1);
        }
        return 0;
}
[/code]

第二题比较简单，就是排序以及判断。先对鬼和捉鬼大师进行y的降序排序，如果y相同就按x的降序排序。然后基本按照如下代码片段进行判断。完全讲清楚，需要画图，挺麻烦，大家不明白的可以提出。
[code=c]
for (int i=0; i<n; ++i) {
                // 找到捉鬼大师的坐标使得 x <= g[i].x && y >= g[i].y
                while(j <m && b[j].y >= g[i].y) {
                        minx= min(minx,b[j].x);
                        ++j;
                }
                if (minx<= g[i].x) continue;
                printf("%d %d\n",g[i].x,g[i].y);
        }
[/code]