UVA 10214 Trees in a Wood. （欧拉函数）

题意：

在满足|x| <= a |y| <= b 的网格中，整点x，y各种着一棵树（扣掉原点），问你从原点能看到多少棵树。

思路：

显然 就是找有几对(x,y) 满足 gcd(x,y) = 1;

因为不等于1的话，肯定在等于1位置的后面，肯定是看不到的。

当 1<= y <= x 有phi(x) 个。 这是欧拉函数的定义。

当x+1 <= y <= 2x 也有phi(x)个 。 这个需要用gcd的 一个性质， 即 gcd(a+mb,b) = gcd(a,b);

依次类推，，

那么我们枚举列显然会更快了。

#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>using namespace std;typedef long long LL;const double eps = 1e-10;int phi[2000000 + 7];LL gcd(LL a,LL b){    return !b ? a : gcd(b,a%b);}void init(){    phi[1] = 1;    for (int i = 2; i < 2000000+7; ++i) if (!phi[i]){        for (int j = i; j < 2000000 + 7 ; j += i){            if (!phi[j]) phi[j] = j;            phi[j] = phi[j] / i * (i-1);        }    }}int n, m;int main(){    init();    while(~scanf("%d %d",&n, &m) && (n || m)){        LL ans = 0;        for (int x = 1; x <= n; ++x){            int y;            for (y = x; y <= m; y += x){                ans += phi[x];            }            y-=x;            if (y < m){                for (int j = y+1; j <= m; ++j){                    if (gcd(j,x) == 1)++ans;                }            }        }        ans*=4;        ans+=4;        LL N = (LL)n*(LL)m*4 + 2*n+2*m;        PRintf("%.10f/n",(ans*1.0)/N + eps);    }    return 0;}