Codeforces Round #153 (Div. 一) C. Number Transformation

Codeforces Round #153 (Div. 1) C. Number Transformation

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

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

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 numbera into numberb. Please note that numbersx 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¹⁸) andk (2 ≤ k ≤ 15).

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

Output

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

Sample test(s)

Input

10 1 4

Output

Input

6 3 10

Output

Input

1000000000000000000 1 3

Output

666666666666666667

Note

In the first sample the sequence of numbers that Petya gets as he tries to obtain numberb 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. a--

2. 在2~k中选择一个数c，a=a-a%c；

就出最小步数。

思路：

因为a、b很大，所以必须要找周期，有一个性质就是a与a+lcm（2~k）对2~k的mod性质都是相同的，可以根据这个性质来优化，令tot=lcm（2~k），设a=x*tot+y，那么此时a%c=y%c，总是在向a=x*tot逼近，最终总会到达a=x*tot这个点。

那么我们就可以分三段来算答案了，

首先a变为x1*tot，相当于a%tot变为0；

然后x1*tot变为x2*tot（比b稍稍大一点），相当于（x1-x2）*（tot变为0）；

然后x2*tot变为b，相当于tot变为b%tot。

所以全部都能转化为一个周期内的变换了，用dp即可解决。

ps：这题数据不强，开始用不是很严密的方法过了，但是不能过238 58 5这个数据，答案为73.

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <queue>
#define maxn 1005
#define MAXN 1000005
#define mod 100000000
#define INF 0x3f3f3f3f
#define pi acos(-1.0)
#define eps 1e-6
typedef long long ll;
using namespace std;

ll n,m,ans,tot,flag;
ll a,b,k,ta,tb;
ll dp[MAXN];

ll gcd(ll x,ll y)
{
    if(y==0) return x;
    return gcd(y,x%y);
}
ll lcm(ll x,ll y)
{
    return x/gcd(x,y)*y;
}
void solve()
{
    ll i,j,t,sub;
    for(i=0; i<=tot; i++) dp[i]=INF;
    dp[0]=0;
    for(j=1; j<=tot; j++)
    {
        for(i=1; i<=k; i++)
        {
            if(i==1) sub=1;
            else sub=j%i;
            dp[j]=min(dp[j],dp[j-sub]+1);
        }
    }
}
ll solve1(ll ta,ll tb)
{
    ll i,j,t,sub;
    for(i=0; i<=ta; i++) dp[i]=INF;
    dp[tb]=0;
    for(j=tb+1; j<=ta; j++)
    {
        for(i=1; i<=k; i++)
        {
            if(i==1) sub=1;
            else sub=j%i;
            dp[j]=min(dp[j],dp[j-sub]+1);
        }
    }
    return dp[ta];
}
int main()
{
    ll i,j,t;
    while(cin>>a>>b>>k)
    {
        tot=1;
        for(i=2; i<=k; i++)
        {
            tot=lcm(tot,i);
        }
        ll num=a/tot-b/tot-1;
        if(num==-1) ans=solve1(a%tot,b%tot);  // 在一个周期内
        else
        {
            solve();
            ll ans2=num*dp[tot];
            ll ans1=solve1(a%tot,0);
            ll ans3=solve1(tot,b%tot);
            ans=ans1+ans2+ans3;
            // printf("num:%lld ans1:%lld ans2:%lld ans3:%lld\n",num,ans1,ans2,ans3);
        }
        cout<<ans<<endl;
    }
    return 0;
}

Codeforces Round #153 (Div. 一) C. Number Transformation

相关推荐