QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#788662 | #9622. 有限小数 | mzyx | WA | 1ms | 3928kb | C++20 | 2.6kb | 2024-11-27 17:48:50 | 2024-11-27 17:48:57 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define gcd __gcd
const int maxd=1E9;
template <class T> T sign(const T &a) {
return a == 0 ? 0 : (a < 0 ? -1 : 1);
}
template <class T> T ceil(const T &a, const T &b) {
T A = abs(a), B = abs(b);
assert(b != 0);
return sign(a) * sign(b) > 0 ? (A + B - 1) / B : -A / B;
}
int exgcd(int a, int b, int &x, int &y) {
if (!b) {
x = 1, y = 0;
return a;
}
int d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
void solve()
{
int a,b,c=1E18,d=0,c1=0,c2=0;
scanf("%lld %lld",&a,&b);
int k=b;
while(k%2==0){k=k/2;c1++;}
while(k%5==0){k=k/5;c2++;}
if(k==1)
{
printf("0 1\n");return;
}
map<int,int> mp;
priority_queue<int,vector<int>,greater<int>> pq;
mp[b]=1;
pq.push(b);
while(!pq.empty())
{
int x=pq.top();pq.pop();
if(5*x<=maxd&&!mp[5*x])
{
mp[5*x]=1;
pq.push(5*x);
}
if(2*x<=maxd&&!mp[2*x])
{
mp[2*x]=1;
pq.push(2*x);
}
int l=0,r=1E18/k;
int y=a*x/b;
while(l<r)
{
int mid=(l+r)/2;
if(mid*k<y){l=mid+1;}
else{r=mid;}
}
while(l*k<y){l++;}
int o=l*k-y;
int m=gcd(o,x);
o=o/m;x=x/m;
if(o<c){c=o;d=x;}
}
auto clac = [&](int a, int b, int c) -> int {
int x, y, d = exgcd(a, b, x, y);
if (c % d != 0) {
return -1;
}
x *= c / d, y *= c / d;
int p = b / d, q = a / d, k;
if (x < 0) {
k = ceil(1 - x, p);
x += p * k;
y -= q * k;
}
else if (x >= 0) { //将x提高到最小正整数
k = (x - 1) / p;
x -= p * k; //将x降低到最小正整数
y += q * k;
}
if (y > 0) { //有正整数解
return x;
} else { //无整数解
return -1;
}
};
for(int i=0;i<=c1;i++)
{
for(int j=0;j<=c2;j++)
{
int x=k*pow(2,i)*pow(5,j);
int y=b/x;
// a/b+c/x y=b/x
// a = k*m-c*x
int res=clac(k,-y,a);
if(res!=-1&&res<c)
{
c=res;
d=x;
}
}
}
printf("%lld %lld\n",c,d);
}
signed main()
{
int tt;
scanf("%lld",&tt);
while(tt--)
{
solve();
}
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3928kb
input:
4 1 2 2 3 3 7 19 79
output:
0 1 1 3 1 14 1 79
result:
wrong answer The result is not terminating.(Testcase 4)