描述 Description
Alice and Bob, both have to drink water. But they both don’t want to go, so they will play a game to decide who will fetch water for both of them. Alice will choose a number randomly between 1 and N (both inclusive) and Bob will choose a number randomly between 1 and M (both inclusive). Both will write their numbers on a slip of paper. If sum of numbers choosen by both is odd, then Alice will go, else Bob will go.
What is probability that Alice will go?
输入格式 InputFormat
First line contains, T, the number of testcases. Each testcase consists of N and M in one line, separated by a space.
输出格式 OutputFormat
For each test case, output a single line containing probability as an irreducible fraction.
样例输入 SampleInput
3
1 1
1 2
2 3
样例输出 SampleOutput
0/1
1/2
1/2
数据范围和注释 Hint
1 ≤ T ≤ 105
1 ≤ N,M ≤ 109
#test1: The only way is when Alice and Bob both choose 1. So, Alice won’t have to go because sum is even.
#test2: The different ways are (1,1) and (1,2), where first term denotes the number choosen by Alice. So of all possible cases (ie. 2) in only 1 case Alice has to go. Therefore, probability is 1/2.
#test3: The different ways are (1,1), (1,2), (1,3), (2,1), (2,2), (2,3) where first term denotes the number choosen by Alice. So of all possible cases (ie. 6) in only 3 cases Alice has to go. Therefore, probability is 1/2.
代码 Code
水。化最简分数求个 gcd。
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define inf 0x7fffffff/27.11
long long i,j,t,n,m,l,r,k,z,y,x;
inline long long odd(long long s)
{
if (s%2==0) return s/2;
else return s/2+1;
}
inline long long even(long long s)
{
return s/2;
}
long long gcd(long long x,long long y)
{
if (y==0) return x;
else return gcd(y,x%y);
}
int main()
{
scanf("%d",&t);
while (t--)
{
scanf("%lld%lld",&n,&m);
x=odd(n)*even(m)+even(n)*odd(m);
y=n*m;
z=gcd(x,y);
printf("%lld/%lldn",x/z,y/z);
}
return 0;
}