QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #742477 | #9622. 有限小数 | Tom22l | TL | 1ms | 3784kb | C++23 | 1.7kb | 2024-11-13 16:41:08 | 2024-11-13 16:41:10 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
int Read(){
int x=0;
char ch=getchar();bool f=0;
while(ch<'0'||ch>'9') if(ch=='-')f=1,ch=getchar(); else if(ch==EOF)return 0; else ch=getchar();
while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return f?-x:x;
}
int res[1000];
int cnt;
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
for(int i=0;i<=60;i++){
int fac5=1;
res[++cnt]=(1ll<<i);
for(int j=1;j<=21;j++){
fac5*=5;
__int128 nw=(__int128)fac5*(1ll<<i);
if((__int128)nw<=(__int128)(1e17)) res[++cnt]=(int)nw;
}
}
sort(res+1,res+cnt+1);
int T=Read();
for(int t=1;t<=T;t++){
int a=Read(),b=Read();
int ansa=b-a,ansb=b;
int x=b;
while(x%2==0)x/=2;
while(x%5==0)x/=5;
if(x==1){
printf("0 1\n");
continue;
}
for(int i=1;i<=cnt;i++){
// if((__int128)a*res[i]>1e18) continue;
int c=x-(a%x)*(res[i]%x)%x;
int g1=__gcd(c,b);
c/=g1;
int g=__gcd(c,res[i]);
if((__int128)((__int128)b*(__int128)res[i])>(__int128)((__int128)1e9*(__int128)g*(__int128)g1));
else if(c/g<ansa){
ansa=c/g;
ansb=b*res[i]/g/g1;
}
c=x-(a%x)*(res[i]%x)%x+x;
g1=__gcd(c,b);
c/=g1;
g=__gcd(c,res[i]);
if((__int128)((__int128)b*(__int128)res[i])>(__int128)((__int128)1e9*(__int128)g*(__int128)g1));
else if(c/g<ansa){
ansa=c/g;
ansb=b*res[i]/g/g1;
}
c=x-(a%x)*(res[i]%x)%x+2*x;
g1=__gcd(c,b);
c/=g1;
g=__gcd(c,res[i]);
if((__int128)((__int128)b*(__int128)res[i])>(__int128)((__int128)1e9*(__int128)g*(__int128)g1));
else if(c/g<ansa){
ansa=c/g;
ansb=b*res[i]/g/g1;
}
}
printf("%lld %lld\n",ansa,ansb);
}
return 0;
}
/*
9946875
*/
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3784kb
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
Time Limit Exceeded
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 7 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 ...