GT and numbers

问题描述

给出两个数NN和MM。

NN每次可以乘上一个自己的因数变成新的NN。

求最初的NN到MM至少需要几步。

如果永远也到不了输出-1−1。

输入描述

第一行读入一个数TT表示数据组数。

接下来TT行，每行两个数NN和MM。

T\leq1000T≤1000, 1\leq N \leq 10000001≤N≤1000000,1 \leq M \leq 2^{63}1≤M≤263.

注意M的范围。hack时建议输出最后一行的行末回车;每一行的结尾不要输出空格。

输出描述

对于每组数据，输出一个数表示答案。

输入样例

输出样例

0

-1

1

题解：对n质数分解成x个指数因子，再对m进行整除到底，知道所得m为1为止，记录步数ans就是答案，否则-1；

///

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#include<queue>

#include<cmath>

#include<map>

#include<bitset>

#include<set>

#include<vector>

using namespace std ;

typedef unsigned long long ll;

#define mem(a) memset(a,0,sizeof(a))

#define meminf(a) memset(a,127,sizeof(a));

#define memfy(a)  memset(a,-1,sizeof(a));

#define TS printf("111111\n");

#define FOR(i,a,b) for( int i=a;i<=b;i++)

#define FORJ(i,a,b) for(int i=a;i>=b;i--)

#define inf 100000000

inline ll read()

{

    ll x=,f=;

    char ch=getchar();

    while(ch<''||ch>'')

    {

        if(ch=='-')f=-;

        ch=getchar();

    }

    while(ch>=''&&ch<='')

    {

        x=x*+ch-'';

        ch=getchar();

    }

    return x*f;

}

//***************************************

#define maxn 1000000+5

  bool P[maxn];

  int k;

  int  prime[maxn];

  vector<int  >V;

  int H[maxn],S[maxn];

  void init()

  {

      P[]=;

    for(int i=;i<=;i++)

      {

          if(!P[i])

          {

              for(int j=i+i;j<=;j=j+i)

                P[j]=;

          }

      }

      k=;

      for(int i=;i<=;i++)

      {

          if(!P[i])

             prime[++k]=i;

      }

  }

 __int64 get( __int64 x,__int64 y)

  {

      __int64 j=;

      while(y<x)

      {

          x-=y;

          j++;

          y+=y;

      }

      if(j==)j++;

      return j;

  }

  int main()

  {

      int T;

      init();

      scanf("%d",&T);

      while(T--)

      {

          V.clear();

          ll n=read();

          ll m=read();

          if(n==m)

          {

              printf("0\n");

              continue;

          }

          if(n>m)

          {

            printf("-1\n");

              continue;

          }

          if(n==)

          {

             printf("-1\n");

              continue;

          }

          if(m%n){

            cout<<-<<endl;

            continue;

          }

          ll tmp=m/n;//cout<<tmp<<endl;

         for(int i=;i<=k;i++)

         {

             while(n%prime[i]==)

             {

                 if(H[prime[i]]==)

                 V.push_back(prime[i]);

                 H[prime[i]]++;

                 n/=prime[i];

             }if(prime[i]>n)break;

         } // for(int i=0;i<V.size();i++)cout<<V[i]<<endl;

        __int64  ans=;

         for(int i=;i<V.size();i++)

         {

             if(tmp%V[i]==) {

                 ll jj=;

                 while(tmp%V[i]==)

                 {

                     tmp/=V[i];

                     jj++;

                 }

                ans=max(ans,get(jj,H[V[i]]));

             }

             H[V[i]]=;

         }

         if(tmp!=){

            printf("-1\n");

         }

         else printf("%I64d\n",ans);

      }

      return ;

  }

代码

巴特西

BestCoder Round #60/HDU 5505 暴力数学

GT and numbers

最新文章

热门文章