QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#672048 | #6440. Xingqiu's Joke | prime-ideal | WA | 384ms | 55168kb | C++20 | 2.1kb | 2024-10-24 15:26:46 | 2024-10-24 15:26:47 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define RN return
#define forw(_,l,r) for(auto _=(l);_<(r);++_)
#define fors(_,r,l) for(auto _=(r);_>(l);--_)
#define fastio cin.tie(0),cout.tie(0),ios::sync_with_stdio(0);
#define int ll
void read(){}
template<typename T,typename...Types>
void read(T&a,Types&...args){
a=0; char c=' ';
while(isspace(c))c=getchar();
while(isdigit(c))a=10*a+c-'0',c=getchar();
read(args...);
}
typedef long long ll;
typedef vector<int> vi;
const int INF=0x3f3f3f3f;
const ll INFL=0x3f3f3f3f3f3f3f3f;
vi plst,flst;
void pgen(int x){
int a=sqrt(x)+10;
forw(i,2,a){
int cnt=0;
while(x%i==0)x/=i,++cnt;
if(cnt)plst.push_back(i);
}if(x!=1)plst.push_back(x);
}
void fgen(int x){
if(x==1){flst={1};RN;}
int p=0;
for(auto q:plst)if(x%q==0)p=q;
int cnt=0;
while(x%p==0)++cnt,x/=p;
fgen(x);
int bas=flst.size(),siz=bas,mult=p;
flst.resize(siz*(cnt+1));
forw(i,0,cnt){
forw(j,0,siz)flst[j+bas]=flst[j]*mult;
bas+=siz,mult*=p;
}
}
int ans;
unordered_map<ll,int> st;
int dfag(int x,int m,int d){
if(d>=ans)RN INF;
int idx=1LL*x*INF+m,ret=INF;
auto pt=st.find(idx);
if(pt!=st.end()){
ret=pt->second+d;
ans=min(ans,ret);
RN ret;
}
int& lk=st[idx];
if(m==1) ret=x+d;
else{
int k=x/m,r=x%m;
for(auto p:plst)if(m%p==0){
ret=min(ret,dfag(r,m/p,d+k+1));
if(r)ret=min(ret,dfag(m-r,m/p,d+k+2));
}}
lk=ret-d;
ans=min(ans,ret);
RN ret;
}
void clear(){
ans=INF;
plst.clear(),flst.clear();
}
void solve(){
int a,b; read(a,b);
int x=a-b; x=x<0?-x:x;
pgen(x); fgen(x);
// for(auto f:flst)cout<<f<<' ';
// cout<<endl;
for(auto y1:{a,b})for(auto y2:flst)
dfag(y1,y2,0);
cout<<ans-1<<'\n';
}
void test(){
pgen(120); fgen(120);
for(auto f:flst)cout<<f<<' ';
cout<<endl;
}
signed main()
{
// test();
int t;read(t);
while(t--){
clear();
solve();
}
RN 0;
}
/*
1
2 1
*/
/*
10
651 806
667 787
243 758
932 572
311 420
596 805
40 581
349 396
496 843
399 751
*/
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3572kb
input:
5 4 7 9 8 32 84 11 35 2 1
output:
2 7 5 4 0
result:
ok 5 number(s): "2 7 5 4 0"
Test #2:
score: -100
Wrong Answer
time: 384ms
memory: 55168kb
input:
300 223528529 446621399 755625805 978718675 257717538 480810408 277875777 54782907 963091558 739998688 282469431 505562301 38752451 261845321 474429597 697522467 67026335 290119205 874629705 651536835 301964126 78871256 316864911 93772041 545942587 322849717 640801578 417708708 683070559 906163429 9...
output:
14 20 15 17 17 17 13 19 17 17 17 15 18 17 17 19 16 18 15 16 17 18 20 16 17 17 18 14 19 20 13 20 16 17 13 18 18 18 16 17 14 17 14 16 15 14 19 19 17 15 16 17 16 19 17 16 17 16 18 18 17 19 20 18 18 16 16 16 23 15 14 20 18 20 16 16 19 18 12 21 19 19 16 19 18 15 18 12 17 18 16 13 19 20 16 18 17 15 15 17 ...
result:
wrong answer 1st numbers differ - expected: '12', found: '14'