题解：P10667 BZOJ2712 [Violet 2] 棒球
qinyiyang2012
·
·
题解
思路分析
设安打次数为 p，打击次数为 q，且 p < q,q \ne 0。
例如安达率四舍五入后为 $0.316$，则 $0.3155 \leqslant \frac{p}{q} < 0.3165$。
注意到这其实是 [P5179 Fraction](https://www.luogu.com.cn/problem/P5179)，我们只需要再处理一下 $r - \frac{5}{10^{n+1}} = \frac{p}{q}$ 的特殊情况即可。
### 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
string r;
ll qpow(ll x,ll y){
ll res=1;
while(y){
if(y&1)res*=x;
x*=x;
y>>=1;
}
return res;
}
void query(ll a,ll b,ll& p,ll& q,ll c,ll d){
if(a<b&&c>d){
p=q=1;
return;
}
query(d%c,c,q,p,b-d/c*a,a);
q+=d/c*p;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
while(cin>>n>>r){
ll x=0,p,q;
for(int i=2;i<r.size();i++)x=x*10+(r[i]-'0');
if(!x){//安达率为0记得特判
cout<<"1\n";
continue;
}
ll a=x*10-5,b=qpow(10,n+1),c=x*10+5,d=qpow(10,n+1);
//处理取等号的情况
ll p1=a,q1=b,g=__gcd(p1,q1);
p1/=g,q1/=g;
query(a,b,p,q,c,d);
cout<<min(q,q1)<<"\n";
}
return 0;
}
```