Gym

(Gym.cpp/c/pas)

题目描述 Description

木吉终于到达了 VAN 様的老巢 gym,然而他已经是孤身一人。他决定和 VAN 様来一场对决。他决定和 VAN 様玩♂跑♂步。已知跑道长$l$米，而木吉一步能跑且只能跑$n$米，VAN様一步能跑且只能跑$m$米。现在规定选手不能跑出$k$米。而谁最后跑得远谁就赢了。出于公平起见，$k$是一个$1 $到$l$之间完全随机的正整数。现在木吉想要知道，自己和 VAN 様打成平局的概率是多少。

输入描述 (gym.in) Input Description

第一行为三个整数，依次为$l,n,m$;

输出描述 (gym.out) Output Description

一个约分后的真分数，格式为a/b，为木吉和 VAN 様打成平局的概率

样例输入 Sample Input

10 3 2

样例输出 Sample Output

3/10

样例解释 Sample Interpretation

当$ k $为$1,6,7 $时，木吉会和 VAN 様打成平局

数据范围 Data Size

对于 30%的数据，$n,m,l\le 10^6$

对于 100%的数据，$n,m,l\le 5\times {10}^{18}$

题解

首先确定这是一道数论题，于是就往此方向想。

显然，木吉和 VAN 様打成平局的充要条件是：$k\mod n=k\mod m$。

不难发现，当$n=m$时，$k$显然成立。而上式会报错，于是需要特判一下：

if(n==m)

{

	fout<<"1/1";

	return 0;

}

然后继续开始愉快的推导……

将上式中$k$转化为带余除式，有$k-t_1 n=k-t_2 m$，$t_1 n=t_2 m$。

设满足木吉和 VAN打成平局的$k$的总数为$ans$。

不难发现，当$k=\infty$时，木吉和 VAN首次相遇是在$[a,b]$处。于是，当$k<[a,b]$时，$ans=\min(m,n)$（两个人都没有跨出一步）。

按照这个思路，我们发现两人在$[a,b]$处与在起点处是等价的。于是我们就不难推出正解。

毒瘤的是$[a,b]$unsigned long long竟存不下……于是在必要情况下必须用long double。

代码

#include <fstream>

#include <algorithm>

using namespace std;

typedef long long LL;

LL l,n,m;

int main()

{

	ifstream fin("gym.in");

	ofstream fout("gym.out");

	fin>>l>>n>>m;

	if(n==m)

	{

		fout<<"1/1";

		fin.close();

		fout.close();

		return 0;

	}

	LL t=min(n,m);

	LL ans=t-1;

	if(ans>l)

	{

		fout<<"1/1";

		fin.close();

		fout.close();

		return 0;

	}

	LL g=__gcd(m,n);

	LL lcm=m/g*n;

	if((long double)m/g*n<=(long double)l)

		ans+=l/lcm*t;

	LL tmp=__gcd(ans,l);

	fout<<ans/tmp<<'/'<<l/tmp;

	fin.close();

	fout.close();

	return 0;

}

巴特西

20180418模拟赛T2——Gym

Gym