关于直线扫描格子问题
有一个n*m(1 <=n,m <=10^6)的格子，在每个格子的中心都有一个人，A在最左下角的格子中，他手中有一把威力很大的枪，一枪可以击中直线上的任何目标，A只能在左下角的格子中，但可以转方向，求其最少开几枪可以将其余n*m-1人打中。我想了好长时间，感觉与欧拉函数有关，但不知怎么做，
谁有思路，帮下忙。 很暴力 还没细想。
假定开枪者枪口指向正上方，
则每次顺时针旋转一个最小的角度，
直到此时该枪口上有人存活则扣动扳机。
似乎所费的子弹已足够少了。:lol :Q:
换一种策略（也许并不好）：
首先应瞄准矩形最外围尚存活的那些人，
由于枪的威力巨大，子弹会顺带干掉矩形内部处在射线上的家伙。
当外围敌人消灭后，矩形就相对瘦了一圈，
继续沿该策略执行下去，就可完成任务。 此问题与以下问题等价：
$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)$
后面的化简就不会了（离开学校多年，很多东西忘记了:L ）。 csdn上出现过的:
http://topic.csdn.net/u/20080907/00/d77747a0-7e7f-4ac4-9f9b-902d54795069.html mathe 在上述链接中给出了非常好的算法。:b:
这里转帖一下：
可以通过一个类似筛选法求素数的算法，计算出所有小于n的数x的不同素因子数目pc
如pc=0,pc=pc=pc=pc=1,pc=2
然后对于每个整数d,我们知道矩形$1 <=x <=n-1,1 <=y <=m-1$中,x,y都是d的倍数的数目是$[(n-1)/d]*[(m-1)/d]$
我们要算的就是for(s=0,i=1;i<min(n,m);i++){
if(pc&1){
s-=((n-1)/i)*((m-1)/i);
}else{
s+=((n-1)/i)*((m-1)/i);
}
}
回复 6# gxqcn 的帖子
真没想到这个都能被你找到，那个帖就是我发的，但是他的方法在第四个测试点上就错了，还忘指点一下。
页:
[1]