CodeForces 592C The Big Race (高精度+數論)

題目連結:http://codeforces.com/problemset/problem/592/C

題目大意

給定一個長度的賽道，

兩個人分别每步隻能走x步和y步，

終點後全是深淵，兩個人不會走到深淵中并且

他們會走到最遠的情況，假設終點長度是x，

其兩人比賽結果相同的，機率是多少，

對于x取值1到p來說。

題目分析 

這題思路不難就是高精度會出問題，

因為資料範圍是以要開無符号整數，

然後這個數的範圍不能出現負數，

直接取lcm會爆炸，嘗試着換成double來比較一波先。

下面說下思路：

我們把每一處lcm及其後面min(b,c)-1長度的點都考慮進去，

然後去除掉超過範圍的一小部分，這個手動判定下即可，詳見代碼，

這題還有個玄學問題，，，我把下面的GCD都替換成gcd函數形式

就過不了了，，，不知道是不是cf評測機精度的問題。。。

這題學到了double處理略大範圍的精度問題蛤。

#include<bits/stdc++.h>
using namespace std;
#define min(x,y) ((x)<(y)?(x):(y))
#define debug puts("YES");
#define rep(x,y,z) for(int (x)=(y);(x)<(z);(x)++)
#define ll long long

#define lrt int l,int r,int rt
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define root l,r,rt
#define mst(a,b) memset((a),(b),sizeof(a))
#define pii pair<int,int>
#define fi first
#define se second
#define mk(x,y) make_pair(x,y)
int mod=20100501;
const int maxn=30+10;
const int ub=1e6;
ll powmod(ll x,ll y){ll t; for(t=1;y;y>>=1,x=x*x%mod) if(y&1) t=t*x%mod; return t;}
ll gcd(ll x,ll y){
    return y?gcd(y,x%y):x;
}
/*
題目大意：
給定一個長度的賽道，
兩個人分别每步隻能走x步和y步，
終點後全是深淵，兩個人不會走到深淵中并且
他們會走到最遠的情況，假設終點長度是x，
其兩人比賽結果相同的，機率是多少，
對于x取值1到p來說。

題目分析：
這題思路不難就是高精度會出問題，
因為資料範圍是以要開無符号整數，
然後這個數的範圍不能出現負數，
直接取lcm會爆炸，嘗試着換成double來比較一波先。
下面說下思路：
我們把每一處lcm及其後面min(b,c)-1長度的點都考慮進去，
然後去除掉超過範圍的一小部分，這個手動判定下即可，詳見代碼，
這題還有個玄學問題，，，我把下面的GCD都替換成gcd函數形式
就過不了了，，，不知道是不是cf評測機精度的問題。。。

這題學到了double處理略大範圍的精度問題蛤。
*/
ll a,b,c;
int main(){
    scanf("%lld%lld%lld",&a,&b,&c);
    ll ans=0,GCD=gcd(b,c);
    if(1.0*b/gcd(b,c)*c>(double)a){
        ans=min(a,min(b-1,c-1));
    }else{
        ll lcm=b/gcd(b,c)*c;
        ll res=a-a/lcm*lcm;
        ans=a/lcm*min(b,c)+min(res,min(b-1,c-1));
    }
    ll gd=gcd(ans,a);
    printf("%lld/%lld\n",ans/gd,a/gd);
    return 0;
}