约数魔方(ct14)问题解答

23魔方(基因检测)v1.0.1 官方版

• 类型：安卓应用电脑版大小：4.4M语言：中文 评分：10.0
• 标签：

立即下载

题目描述：
我们知道，一个数K若能被除开1和它本身外的数整D除，这个数就叫做合数
D就叫做K的一个约数。现在进行一个游戏，每一数都能加上它的除1和本身
外的一个约数D从而变成另外一个数。现在给你两个数N，M，问从N到M最少
要进行多少次加法的操作.如果按照上面的操作从N不能到达M，则输出-1

输入：
多组测试数据，每组一行两个数 N， M (4<=N<=M<=100000)
以EOF结束输入

输出：
上面那个问题的结果

样例输入：
4 24
4 576

样例输出：
5
14

其它信息：
Contest 14 比赛题
题目提供：ailyanlu

难度：Normal

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<ctime>
using 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;
}