//到达2 , 3 … k的最小公倍数为lcm//当x到达lcm的倍数时，，x只能减一//又从a到b一定会过lcm的倍数//我们将a,b以lcm分割//那么完整的lcm段的最小数是相同的，所以我们只需要计算一个lcm段的最小值乘以完整lcm段的个数//以及首尾的不全的lcm段的和即为答案#include<cstdio>#include<cstring>#include<iostream>#include<queue>using namespace std ;const int maxn = 1000010 ;int vis[maxn] ;struct node{ __int64 step; __int64 value ;};int gcd(int a , int b){ if(a < b) swap(a,b); if(b == 0) return a ; return gcd(b, a%b) ;}int lcm(int a,int b){ return a*b/gcd(a,b) ;}queue<struct node>que;__int64 bfs(__int64 n ,__int64 k ,__int64 en){ while(que.size())que.pop(); struct node first = {0,n} ; que.push(first) ; vis[n] = 1; memset(vis, 0 ,sizeof(vis)) ; while(que.size()) { struct node now = que.front() ; que.pop() ; if((__int64)now.value == en) return now.step; for(int i = 1;i <= k;i++) { __int64 t ; if(i == 1)t = now.value – 1; else t = now.value – now.value%i; if(t<0 || vis[t])continue ; struct node next = {now.step+1 , t} ; que.push(next) ; vis[t] = 1; } } return 0;}int main(){ //freopen("input.txt","r",stdin) ; __int64 a , b , k; while(~scanf("%I64d%I64d%I64d" ,&a ,&b ,&k)) { int sum= 2; if(k == 2) { printf("%I64d\n" ,a – b) ; continue ; } for(int i = 3;i <= k;i++) sum = lcm(sum , i) ; __int64 first = (b+(__int64)sum-1)/(__int64)sum; __int64 last = a/(__int64)sum; __int64 ans ; if(last >= first) { ans=(last – first)*(bfs((sum-1) , k , 0) + 1); ans += bfs(sum,k,b%sum); ans += bfs(a%sum,k,0); } else ans = bfs(a%sum, k ,b%sum); printf("%I64d\n" ,ans) ; }}
就是对虚怀若谷谦虚谨慎八个字真正理解的人，
