J. Xingqiu‘s Joke

​​傳送門​​

題意：

思路：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll pri[100100];
int vis[100100];
unordered_map<ll,ll>f;
ll change(ll a,ll b)
{
  return a*1e9+b;
}
int cnt;
void oula()
{
  for(int i = 2; i <= 100000; i++)
  {
    if(!vis[i])pri[++cnt] = i;
    for(int j = 1; j <= cnt && pri[j]*i <= 100000; j++)
    vis[i*pri[j]] = 1;
  }
}
int dpri[100100];
int cot;
int dfs(ll a,ll d)
{
  
//  cout<<a<<" "<<d<<"\n";
  if(a == 1)return 0;
  else if(f[change(a,d)])return f[change(a,d)];
  if(d == 1)return a-1;
  ll now = a-1;
  for(int i = 1; i <= cot; i++)
  {
    if(d%dpri[i] == 0)
    now = min(now,1+min(dfs(a/dpri[i]+1,d/dpri[i])+dpri[i]-a%dpri[i], dfs(a/dpri[i], d/dpri[i])+a%dpri[i]));
  }
  return f[change(a,d)]=now;
}
int main()
{
  oula();
  int t;
  cin>>t;
  while(t--)
  {
    ll a,b;
    cin>>a>>b;
    cot = 0; 
    if(a > b)swap(a,b);
    ll d = b-a;
    for(int i = 1; i <= cnt && pri[i] <= d; i++)
    {
      if(d%pri[i] == 0)dpri[++cot] = pri[i];
      while(d%pri[i] == 0)
      {
        d/=pri[i];
      }
    }
    if(d>1)dpri[++cot] = d;
    cout<<dfs(a,b-a)<<endl;
  }
}