QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#745643 | #9622. 有限小数 | Chen1098 | TL | 66ms | 3640kb | C++14 | 2.2kb | 2024-11-14 10:55:18 | 2024-11-14 10:55:19 |
Judging History
answer
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,##__VA_ARGS__)
#define int long long
#define endl '\n'
#define pb push_back
#define pii pair<int,int>
using namespace std;
bool Men;
const int mod=998244353;
const int N=200005;
inline void write(int x){if(x<0) putchar('-'),x=-x;if(x>9) write(x/10);putchar(x%10+'0');return;}
inline int read() {int x=0,f=1; char ch=getchar();while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar();}while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();return x*f;}
void add(int &x,int y){x=(x+y)%mod;}
int ksc(int m,int n,int p){int ans=0;while(n){if(n%2==1){n=n-1;ans=(ans+m)%p;}n=n/2;m=(m+m)%p;}return ans;}
int ksm(int base,int power,int p){int result=1;while(power>0){if(power&1){result=result*base%p;}power>>=1;base=(base*base)%p;}return result;}
int mod_inverse(int a){return ksm(a,mod-2,mod);}
int inv(int numerator,int denominator){int inverse_denominator = mod_inverse(denominator);int result=(1LL*numerator*inverse_denominator)%mod;return result;}
int a,b;
bool Mbe;
signed main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int T=read();
while(T--){
a=read(),b=read();
int tot=1,nowb=b,nowa=a;
while(nowb%2==0){
if(nowb%2!=0) break;
nowb/=2;
tot*=2;
}
while(nowb%5==0){
if(nowb%5!=0) break;
nowb/=5;
tot*=5;
}
int must=b/tot;
if(tot!=1&&(a%must==0)){
cout<<0<<' '<<1<<endl;
continue;
}
// cout<<"SDF";
int c=1e9,d=1e9;
for(int i=1;i<=1000000000;i++){
if(b*i>=1e9) break;
int nowb=b*i,tot=1;
while(nowb%2==0){
if(nowb%2!=0) break;
nowb/=2;
tot*=2;
}
while(nowb%5==0){
if(nowb%5!=0) break;
nowb/=5;
tot*=5;
}
if(tot==1) continue;
// cout<<"TOT "<<tot<<endl;
//分子需要形成tot或者其倍数
int nowa=a*i;
nowb=b*i;
int must=nowb/tot;
for(int j=(int)((nowa+must-1)/must);j<=((c+nowa)/must);j++){
int nowmust=must*j;
if(nowmust<=nowa) continue;
if(nowmust-nowa<c){
c=nowmust-nowa;
d=nowb;
}
else break;
}
if(c==1) break;
}
cout<<c<<' '<<d<<endl;
}
/*
2 5
1
28 53
*/
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 66ms
memory: 3640kb
input:
4 1 2 2 3 3 7 19 79
output:
0 1 1 12 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...