QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#672048#6440. Xingqiu's Jokeprime-idealWA 384ms55168kbC++202.1kb2024-10-24 15:26:462024-10-24 15:26:47

Judging History

你现在查看的是最新测评结果

  • [2024-10-24 15:26:47]
  • 评测
  • 测评结果:WA
  • 用时:384ms
  • 内存:55168kb
  • [2024-10-24 15:26:46]
  • 提交

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'