3506 - 喵呜B
最近蓝翔火了，因此喵星派了小喵呜到蓝翔交流开挖掘机经验，当然交流完之后也没忘了去汪星得瑟一下，但是汪星早有准备，他们临时颁布了个法令，开挖掘机上路需要交过路费。
现在假设汪星的城市由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; }