当前位置: 代码迷 >> 综合 >> CodeForces 592C The Big Race (高精度+数论)
  详细解决方案

CodeForces 592C The Big Race (高精度+数论)

热度:60   发布时间:2023-11-15 11:45:03.0

题目链接: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;
}