关于直线扫描格子问题

zhuceyongde

有一个n*m(1 <=n,m <=10^6)的格子，在每个格子的中心都有一个人，A在最左下角的格子中，他手中有一把威力很大的枪，一枪可以击中直线上的任何目标，A只能在左下角的格子中，但可以转方向，求其最少开几枪可以将其余n*m-1人打中。

我想了好长时间，感觉与欧拉函数有关，但不知怎么做，
谁有思路，帮下忙。

无心人

很暴力

gxqcn

还没细想。

假定开枪者枪口指向正上方，
则每次顺时针旋转一个最小的角度，
直到此时该枪口上有人存活则扣动扳机。
似乎所费的子弹已足够少了。

换一种策略（也许并不好）：
首先应瞄准矩形最外围尚存活的那些人，
由于枪的威力巨大，子弹会顺带干掉矩形内部处在射线上的家伙。
当外围敌人消灭后，矩形就相对瘦了一圈，
继续沿该策略执行下去，就可完成任务。

sunwukong

此问题与以下问题等价：

$1 <= x <= n$

$1 <= y <= m$

$x$,$y$ 互素

求 $(x,y)$ 的个数

由欧拉函数的定义：

如果 $N$ 的素因子分解式为

$ N= p_1^{alpha_1}*p_2^{alpha_2}*...*p_t^{alpha_t} $

则

$phi(N)=$  小于或等于 $N$ 的数中与 $N$ 互素的数的数目  $=N*(1-1/p_1)*(1-1/p_2)*...*(1-1/p_t) $

假设 $n<=m$

则所求数为：

$phi(1)+2*(phi(2)+...+phi(n))+phi(n+1)+phi(n+2)+...+phi(m)$

后面的化简就不会了（离开学校多年，很多东西忘记了 ）。

mathe

csdn上出现过的:
http://topic.csdn.net/u/20080907 ... b-902d54795069.html

gxqcn

mathe 在上述链接中给出了非常好的算法。

这里转帖一下：

可以通过一个类似筛选法求素数的算法，计算出所有小于n的数x的不同素因子数目pc[x]
如pc[1]=0,pc[2]=pc[3]=pc[4]=pc[5]=1,pc[6]=2
然后对于每个整数d,我们知道矩形$1 <=x <=n-1,1 <=y <=m-1$中,x,y都是d的倍数的数目是$[(n-1)/d]*[(m-1)/d]$
我们要算的就是

1. for(s=0,i=1;i<min(n,m);i++){
   
2.         if(pc[i]&1){
   
3.                 s-=((n-1)/i)*((m-1)/i);
   
4.         }else{
   
5.                 s+=((n-1)/i)*((m-1)/i);
   
6.         }
   
7. }

复制代码

zhuceyongde

真没想到这个都能被你找到，那个帖就是我发的，但是他的方法在第四个测试点上就错了，还忘指点一下。