题目描述：我们知道，一个数K若能被除开1和它本身外的数整D除，这个数就叫做合数D就叫做K的一个约数。现在进行一个游戏，每一数都能加上它的除1和本身外的一个约数D从而变成另外一个数。现在给你两个数N，M，问从N到M最少要进行多少次加法的操作.如果按照上面的操作从N不能到达M，则输出-1输入：多组测试数据，每组一行两个数 N， M (4<=N<=M<=100000)以EOF结束输入输出：上面那个问题的结果样例输入：4 244 576样例输出：514其它信息：Contest 14 比赛题题目提供：ailyanlu难度：Normal

#include#include#include#includeusing namespace std;const int maxn = 100001 ;int mark[maxn] ;int myq[maxn] ;bool isprimer[maxn];void getprimer(){int i , j ;memset(isprimer,true,sizeof(isprimer));for(i = 2 ; i < maxn/i ; ++i)if(isprimer){for(j = i*i ; j < maxn ; j+= i )isprimer[j] = false ;}}int solve(int N ,int M ){int i ;memset(mark, -1 ,sizeof(mark));int first = 0 , tail = 0 ;myq[first] = N ;mark[N] = 0 ;if(mark[M] != -1 )return mark[M];if(isprimer[N] || isprimer[M])return -1 ;while(first <= tail){int k = myq[first] ;for( i = 2 ; i <= k/i ; ++i)if(k%i==0){if(k+i < maxn){if(mark[k+i] == -1 || mark[k+i] > mark[k]+1){++tail;myq[tail] = k+i;mark[k+i] = mark[k] + 1 ;}}if(k + k/i < maxn){if(mark[k+k/i] == -1 || mark[k+k/i] > mark[k] +1){++tail;myq[tail] = k+k/i;mark[k+k/i] = mark[k] + 1 ;}}if(mark[M] != -1)return mark[M];}++first ;}return mark[M];}int main(){//freopen("datain4.txt","r",stdin);//freopen("dataout4_v4.txt","w",stdout);int N , M ;getprimer();while(scanf("%d%d",&N,&M)!=EOF){printf("%d\n",solve(N,M));}//printf("time = %d\n",clock());return 0;}