QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #767270 | #9622. 有限小数 | xjt05 | WA | 239ms | 3980kb | C++23 | 1018b | 2024-11-20 20:24:14 | 2024-11-20 20:24:23 |
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);
}
ll ksm(ll x,ll y)
{
ll ans=1;
while(y)
{
if(y&1)
ans*=x;
x*=x;
y>>=1;
}
return ans;
}
void solve(){
ll c=1e18;
ll a,b;
ll fenmu=0;
scanf("%lld %lld",&a,&b);
ll u,f;
u=f=LONG_MAX;
for(ll i=0;i<=30;i++){
ll five=1;
for(ll j=0;j<=13;j++,five*=5){
__int128 ko;
ko=(__int128)a*(__int128)ksm(2,i)*(__int128)ksm(5,j);
if(ko>1e18)
break;
ll tem=a*(1<<i)*five;
ll m;
if(tem<=b)
m=(b/tem);
else
m=(tem/b)+(tem%b>0);
c = m*b-tem;
fenmu=b*(1<<i)*five;
ll k=gcd(c,fenmu);
if(fenmu/k>(ll)1e9)
continue;
if(u>c/k)
u=c/k,f=fenmu/k;
else if(u==c/k)
f=min(f,fenmu/k);
else
continue;
}
}
cout<<(ll)u<<" "<<(ll)f<<"\n";
}
int main(){
ll t;
cin>>t;
while(t--){
solve();
}
return 0;
}
/*
10
2 35
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3716kb
input:
4 1 2 2 3 3 7 19 79
output:
0 1 1 3 1 14 3 316
result:
ok 4 case(s)
Test #2:
score: -100
Wrong Answer
time: 239ms
memory: 3980kb
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 54272 1 60 1 56 1 231680000 23 3936 1 36096000 5 326 1 63360 0 1 1 31232 0 1 1 4880 1 10750 1 18500 1 11714560 1 331250 1 2944 1 31 1 6 1 289600000 1 455000 1 58880 1 51840 0 1 1 304 0 1 1 415 1 19328000 1 765000000 1 4640 1 608 1 72192 3 775 1 48 3 347500 1 944 1 43600 1 76 1 430000 1 6336 1...
result:
wrong answer Integer -96812299607605248 violates the range [1, 10^9]