关于直线扫描格子问题

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

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