题意:
给你两个数a, b (1 ≤ b ≤ a ≤ 1018)
和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<cm的最小步数。剩下就bfs把a变成b需要多少步就行了。
详细见代码:
#include<bits/stdc++.h> 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(head<tail) { if(q[head]==ed) return sp[head]; for(i=2;i<=k;i++) { if(!vis[q[head]-q[head]%i]) { vis[q[head]-q[head]%i]=1; q[tail]=q[head]-q[head]%i; sp[tail++]=sp[head]+1; } } if(!vis[q[head]-1]) { vis[q[head]-1]=1; q[tail]=q[head]-1; sp[tail++]=sp[head]+1; } head++; } return -1; } int main() { int i,mc; long long a,b,df,ans,rep; while(~scanf("%I64d%I64d%d",&a,&b,&k)) { mc=1,ans=0; for(i=2;i<=k;i++) mc=(mc*i)/gcd(mc,i); for(i=1;i<mc;i++) dp[i]=-1; dp[0]=0; for(i=1;i<mc;i++) dfs(i); if(a-a%mc>b) 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; }