游客 注册 | 登录
中文 | En

3506 - 喵呜B

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

最近蓝翔火了，因此喵星派了小喵呜到蓝翔交流开挖掘机经验，当然交流完之后也没忘了去汪星得瑟一下，但是汪星早有准备，他们临时颁布了个法令，开挖掘机上路需要交过路费。

        现在假设汪星的城市由n*m的格子组成，法令规定，进入每个格子都要交1汪元过路费，但是，现在小喵呜开着挖掘机在(1, 1)格子的中心，需要开到(n, m)格子的中心，但是很不幸，因为挖掘机从喵星运到汪星，方向盘坏了，只能走直线。现在，他想知道，他总共需要交多少汪元的过路费。 

<p class="p0">
	<p class="p0">
		<span style="font-size:11.0000pt;font-family:'宋体';">例如，当<span>n=3</span><span>，</span><span>m=5</span><span>时，需要交</span><span>7</span><span>汪元的过路费（因为要路过涂色的格子，共有</span><span>7</span><span>格，因此需要交</span><span>7</span><span>汪元）。</span></span>
	</p>


</p>
<p class="p0">
	<p class="p0">
		<span style="font-size:11.0000pt;font-family:'宋体';">当然，如果是经过了格子的交界处，这并不属于任何一个格点，因此不需要交过路费，例如<span>n=m=3</span><span>，只需要交</span><span>3</span><span>汪元的过路费。</span></span>
	</p>



</p>

题目输入

第一行输入一个数T，表示测试数据个数，对于每组测试数据，输入两个数n、m，表示汪星的城市大小(0<n,m<=1000)

题目输出

输出T行，每一行表示一组测试数据的答案，对于每组测试数据，输出一个数，表示小喵呜需要交的过路费数。


输入/输出样例

输入格式

3
3 5
3 3
1 5

输出格式

7
3
5

C语言解答

#include<stdio.h>
#include<math.h>
int n,m;
double f(double x)
{
	if(x==0)return 0;
	return (n-1)*(x-0.5)/(m-1)+0.5;
}
int equal(double a,double b)
{
	return (a<b+0.000000001)&&(a>b-0.000000001);
}
int main()
{
	int t,ans;
	int i;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&m);
		if(m==1){printf("%d\n",n);continue;}
		ans=0;
		for(i=1;i<m;i++)
		{
			if(equal(f(i),(int)f(i)))ans+=(int)f(i)-(int)f(i-1);
			else ans+=(int)f(i)-(int)f(i-1)+1;
		}
		ans+=(int)f(m-0.5)-(int)f(m-1)+1;
		printf("%d\n",ans);
	}
	return 0;
}

C++解答

#include <stdio.h>

int gcd(int x,int y)
{
    return y==0?x:gcd(y,x%y);
}

int main()
{
    //freopen("b.in","r",stdin);
    //freopen("b.out","w",stdout);
    int i,j,n,m,g,T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        n--;m--;g=gcd(n,m);
        printf("%d\n",n+m-(n/g%2==m/g%2?g:0)+1);
    }
    return 0;
}
请先登陆