QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #737354 | #9622. 有限小数 | 3071752286 | WA | 457ms | 3848kb | C++14 | 1.6kb | 2024-11-12 15:36:09 | 2024-11-12 15:36:10 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
unsigned long long maxf=1e15;
unsigned long long a,b,c,d,e,f;
unsigned long long qu(unsigned long long x,unsigned long long y)
{
unsigned long long res=1;
while(y!=0)
{
if(y%2==1) res=res*x;
y/=2;
x=x*x;
}
return res;
}
unsigned long long twocut(unsigned long long l,unsigned long long r,unsigned long long x)
{
if(r-l<=1)
{
if(l*b>x*a) return l;
else return r;
}
unsigned long long mid=(l+r)/2;
if(b*mid>x*a) return twocut(l,mid,x);
else return twocut(mid,r,x);
}
unsigned long long gcd1(unsigned long long x,unsigned long long y)
{
if(x<y) swap(x,y);
unsigned long long res;
while(y!=0)
{
res=x;
x=y;
y=res%y;
}
return x;
}
int main()
{
unsigned long long T;
cin>>T;
while(T--)
{
unsigned long long minc=1e16,mind;
cin>>a>>b;
unsigned long long bb=b;
while(bb%5==0) bb/=5;
while(bb%2==0) bb/=2;
if(bb==1)
{
cout<<0<<" "<<1<<endl;
continue;
}
for(unsigned long long i=0;i<=(unsigned long long)(log(maxf)/log(5));i++)
{
for(unsigned long long j=0;j<=(unsigned long long)(log(maxf)/log(2))&&qu(2,i)*qu(5,j)<=maxf;j++)
{
f=qu(2,i)*qu(5,j);
e=twocut(1,f,f);
d=b*f;
if(b*e<=f*a) break;
unsigned long long gcdd=gcd1(b*e-f*a,d);
c=(b*e-f*a)/gcdd;
d=d/gcdd;
if(minc>c&&d<=1e9)
{
minc=c;
mind=d;
}
// if(f==2) cout<<a<<" "<<b<<" "<<c<<" "<<d<<" "<<e<<" "<<f<<" "<<minc<<" "<<" "<<mind<<endl;
}
}
cout<<minc<<" "<<mind<<endl;
}
return 0;
}
/*
99
1 2
2 3
3 7
19 79
28 53
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3688kb
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: 457ms
memory: 3848kb
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 1 7 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 1484375 0 1 1 415 1 235937500 1 765000000 1 181250 1 2968750 1 4406250 3 775 1 12000 3 347500 1...
result:
wrong answer Jury found better answer than participant's 1 < 2 (Testcase 394)