QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #796724 | #9622. 有限小数 | AdisFD | WA | 27ms | 3656kb | C++14 | 1.0kb | 2024-12-02 00:54:15 | 2024-12-02 00:54:15 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
int T,a,b,c,ans,ans1,ans2,gd1;
int i1,i2;
int gcd(int a1,int b1){
int c1=a1%b1;
while(b1!=0){
c1=a1%b1;
a1=b1;
b1=c1;
}
return a1;
}
int dfs(int a1,int b1,bool b2){
int gd=1;
if(b1>2000000000)return 0;
if(ans==1)return 0;
gd=gcd(c-(a1%c),b1);
if((c-(a1%c))/gd<ans){
ans=(c-(a1%c))/gd;
ans1=b1/gd;
}
if(b2==0)dfs(a1*2,b1*2,0);
dfs(a1*5,b1*5,1);
return 0;
}
signed main(){
cin>>T;
for(int I=1;I<=T;I++){
cin>>a>>b;
c=b;
while(c%2==0)c/=2;
while(c%5==0)c/=5;
if(c==1){
cout<<"0 1"<<endl;
continue;
}
ans=c+1;
dfs(a,b,0);
for(int i=1;i<=b/c;i++){
i1=i;
while(i1%2==0)i1/=2;
while(i1%5==0)i1/=5;
if(i1!=1)continue;
i1=i*c;
for(int j=1;j<i1;j++){
ans2=j*(b/i1)+a;
ans2=c-(ans2%c);
if(ans2==c){
gd1=gcd(j,i1);
if(j/gd1<ans){
ans=j/gd1;
ans1=i1/gd1;
}
}
}
}
cout<<ans<<" "<<ans1<<endl;
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3656kb
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: 27ms
memory: 3572kb
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 4 1591796875 1 6336000 0 1 1 31232 0 1 1 4880 1 44032 1 757760 1 11714560 1 53000000 1 2944 1 31 1 6 1 289600000 1 1863680000 1 120586240 1 331776000 0 1 1 304 0 1 1 25937500 1 19328000 1 765000000 1 475136000 1 608 1 72192 3 812646400 1 48 3 3475...
result:
wrong answer Integer 1591796875 violates the range [1, 10^9]