約數(shù)魔方(ct14)問題解答

23魔方(基因檢測)v1.0.1 官方版

• 類型：安卓應用電腦版大�。�4.4M語言：中文 評分：10.0
• 標簽：

立即下載

題目描述：
我們知道，一個數(shù)K若能被除開1和它本身外的數(shù)整D除，這個數(shù)就叫做合數(shù)
D就叫做K的一個約數(shù)�，F(xiàn)在進行一個游戲，每一數(shù)都能加上它的除1和本身
外的一個約數(shù)D從而變成另外一個數(shù)。現(xiàn)在給你兩個數(shù)N，M，問從N到M最少
要進行多少次加法的操作.如果按照上面的操作從N不能到達M，則輸出-1

輸入：
多組測試數(shù)據，每組一行兩個數(shù) 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;
}