QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #766402 | #9622. 有限小数 | tsai | WA | 56ms | 4088kb | C++14 | 639b | 2024-11-20 17:12:50 | 2024-11-20 17:12:51 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//lg2=30
//log5=19
ll gcd(ll a,ll b){
if(b==0)return a;
else return gcd(b,a%b);
}
void solve(){
ll c=1e18;
ll a,b;
ll fenmu=0;
scanf("%lld %lld",&a,&b);
for(ll i=0;i<=30;i++){
ll five=1;
for(ll j=0;j<=13&&max(a,b)*pow(2,i)*pow(5,j)<1e9+50;j++,five*=5){
ll tem=a*(1<<i)*five;
ll m=(ll)ceil(tem*1.0/b);
if(m*b-tem<c){
c = min(c,m*b-tem);
fenmu=b*(1<<i)*five;
}
}
}
ll j=gcd(c,fenmu);
cout<<c/j<<" "<<fenmu/j<<"\n";
}
int main(){
int t;
scanf("%d",&t);
while(t--){
solve();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 4088kb
input:
4 1 2 2 3 3 7 19 79
output:
0 1 1 3 1 4375 3 316
result:
ok 4 case(s)
Test #2:
score: -100
Wrong Answer
time: 56ms
memory: 4072kb
input:
10000 11 12 28 53 17 60 2 35 17 181 80 123 68 141 79 163 71 99 13 64 33 61 15 32 16 61 11 86 33 74 128 143 40 53 7 23 30 31 5 6 86 181 73 91 13 23 71 81 1 2 7 38 117 160 33 83 129 151 88 153 25 58 16 19 19 141 95 124 43 96 71 139 11 59 106 109 93 152 34 43 17 99 1 57 20 159 16 25 5 73 159 170 172 17...
output:
1 12 1 828125000 1 60 3 560 1 231680000 23 960937500 1 36096000 5 326 1 63360 0 1 1 61000 0 1 1 4880 1 10750 1 18500 1 11714560 1 331250 1 898437500 1 31 1 6 1 289600000 1 455000 1 115000000 1 1265625 0 1 1 29687500 0 1 1 415 1 235937500 1 765000000 1 181250 1 2968750 1 4406250 3 24800 1 12000 3 347...
result:
wrong answer Jury found better answer than participant's 1 < 3 (Testcase 4)