codeforces 251C Number Transformation(數論)

codeforces 251C Number Transformation(數論)

Little Petya likes positive integers a lot. Recently his mom has presented him a positive integer a. There's only one thing Petya likes more than numbers: playing with little Masha. It turned out that Masha already has a positive integer b. Petya decided to turn his number a into the number b consecutively performing the operations of the following two types:

1. Subtract 1 from his number.
2. Choose any integer x from 2 to k, inclusive. Then subtract number (a mod x) from his number a. Operation amod x means taking the remainder from division of number a by number x.

   Petya performs one operation per second. Each time he chooses an operation to perform during the current move, no matter what kind of operations he has performed by that moment. In particular, this implies that he can perform the same operation any number of times in a row.

   Now he wonders in what minimum number of seconds he could transform his number a into number b. Please note that numbers x in the operations of the second type are selected anew each time, independently of each other.

   Input

   The only line contains three integers a, b (1?≤?b?≤?a?≤?10¹⁸) and k (2?≤?k?≤?15).

   Please do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, coutstreams or the %I64d specifier.

   Output

   Print a single integer — the required minimum number of seconds needed to transform number a into number b.

   Sample test(s) input

   10 1 4
   

   output

   6
   

   input

   6 3 10
   

   output

   2
   

   input

   1000000000000000000 1 3
   

   output

   666666666666666667
   

   Note

   In the first sample the sequence of numbers that Petya gets as he tries to obtain number b is as follows: 10 ?→? 8 ?→? 6 ?→? 4 ?→? 3 ?→? 2 ?→? 1.

   In the second sample one of the possible sequences is as follows: 6 ?→? 4 ?→? 3.

   題意：

   給你兩個數a, b (1?≤?b?≤?a?≤?10¹⁸) 和k(2?≤?k?≤?15).。要你把a變成b。你可以進行兩種操作

   1.把a-1.

   2.a-(a%c).2<=c<=k.

   每步只能執行兩種操作的一種。c可以隨意選擇。

   現在問你最少需要多少步把a變成b.

   思路：

   由於數據范圍比較大不能簡單的搜索。必須找找其他的規律了。

   操作1沒什麼好說的。對於操作2.對於每個c肯定就是把a變成c的倍數了。設cm為2~k的最小公倍數。a=x*cm+y。當y=0時操作2已經無效了。此時必須使用操作1.使a減小最快的方法是先把a變成x*cm然後減-1.然後減成(x-1)*cm然後循環。用dp[i]表示。把i減成0需要的最小步數。那沒執行一個上述操作需要的步數就為1+dp[cm-1]。所以可以直接計算出把a減到a-b

   詳細見代碼：

   #include
   using namespace std;
   const int INF=0x3f3f3f3f;
   const double eps=1e-8;
   const double PI=acos(-1.0);
   const int maxn=370360;
   int dp[maxn],k,vis[maxn],sp[maxn],head,tail;
   long long q[maxn];
   int gcd(int x,int y)
   {
       int tp=x%y;
       while(tp)
       {
           x=y;
           y=tp;
           tp=x%y;
       }
       return y;
   }
   int dfs(int x)
   {
       int tp=INF,i;
       if(dp[x]!=-1)
           return dp[x];
       for(i=2;i<=k;i++)
           if(x%i!=0)
               tp=min(dfs(x-x%i),tp);
       tp=min(dfs(x-1),tp);
       return dp[x]=tp+1;
   }
   int bfs(int st,int ed)
   {
       int i;
       memset(vis,0,sizeof vis);
       head=tail=0;
       vis[st]=1;
       q[tail]=st;
       sp[tail++]=0;
       while(headb)
               ans+=dp[a%mc],a-=a%mc;
           df=a-b;
           rep=df/mc;
           a=a-rep*mc;
           ans+=rep*(1+dp[mc-1]);
           df=a-b;
           if(df>0)
           {
               if(a%mc==0)
                   ans+=bfs((a-1)%mc,b%mc)+1;
               else
                   ans+=bfs(a%mc,b%mc);
           }
           printf("%I64d\n",ans);
       }
       return 0;
   }