51nod 1180 方格射击游戏

M*N的方格矩阵，一个人在左下角格子的中心，除他所站位置外，其他格子的中心都有一个敌人，他一次可发射一枚子弹干掉一条直线上的所有敌人，问至少要发射多少子弹才能干掉所有敌人。

Input

输入2个数m, n，中间用空格分隔，对应矩阵的大小。(1 <= m,n <= 5 * 10^6)

Output

输出发射子弹的数量。


首先，我们知道有一个结论，从坐标(0,0)到整点(x,y)连一条线段，经过的整点个数有gcd(x,y)+1
个，包括(0,0)和(x,y)这2个。
对于每一个坐标(x,y)，我们需要考虑是不是需要专门去向它打一枪
需要专门向(x,y)打一枪，说明(0,0)到(x,y)之间没有其他点挡着，即这条线段的整点数只有2个，
即gcd(x,y) + 1 = 2,即gcd(x,y) = 1
所以，如果坐标(x,y)满足gcd(x,y) = 1,则对答案贡献为1
则得到公式
ans = Σ0<=i<=n-1Σ0<=j<=m-1[gcd(i,j) = 1]
    = 2 + ∑1<=i<=n-1∑1<=j<=m-1[gcd(i,j) = 1]
令n=n-1,m=m-1,且n<=m，则：
ans = 2 + ∑1<=i<=n∑1<=j<=m[gcd(i,j) = 1]
令f(d)表示1<=i<=n,1<=j<=m,中gcd(i,j) = d的(i,j)对数
  g(d)表示1<=i<=n,1<=j<=m,中gcd(i,j)为d的倍数的(i,j)对数
则有：
g(d) = (n / d) * (m / d)
g(d) = f(d) + f(2*d) + ... + f(n/d * d)
     = ∑d|kf(k)
则有：
f(d) = ∑d|kmu(k/d) * g(k)
f(1) = ∑1<=k<=nmu(k) * g(k)
ans = 2 + f(1)
所以只需要求f(1)就可以了，可以O(n)求，也可以O(sqrt(n))
特判:
n == 1 && m == 1 ans = 0

                                            
  //File Name: nod1180.cpp
  //Created Time: 2017年01月02日 星期一 18时23分52秒
                                   
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int MAXN = 5000000 + 2;
int prime[MAXN / 10],mu[MAXN];
bool check[MAXN];
void init(int N){
    memset(check,false,sizeof(check));
    int tot = 0;
    mu[1] = 1;
    for(int i=2;i<=N;++i){
        if(!check[i]){
            prime[tot++] = i;
            mu[i] = -1;
        }
        for(int j=0;j<tot;++j){
            if((LL)i * prime[j] > N) break;
            check[i * prime[j]] = true;
            if(i % prime[j] == 0){
                mu[i * prime[j]] = 0;
                break;
            }
            else
                mu[i * prime[j]] = -mu[i];
        }
    }
    for(int i=1;i<=N;++i)
        mu[i] += mu[i - 1];
}
LL solve(int n,int m){
    if(n == 1 && m == 1) return 0;
    if(n == 1 || m == 1) return 1;
    --n,--m;
    if(n > m) swap(n,m);
    init(n);
    LL res = 2;
    for(int i=1,x,y,r;i<=n;){
        x = n / i;
        y = m / i;
        r = min(n / x,m / y);
        res += 1LL * (mu[r] - mu[i-1]) * x * y;
        i = r + 1;
    }
    return res;
}
int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    printf("%lld
",solve(n,m));
    return 0;
}