2019 gc 六年级 第二题 最大步数

题目描述给出了两个非负整数P和Q。您的任务是使得P和Q相等。在每一步中您可以执行以下两项操作之一1、将任何质数加到P上。2、从Q减去任何质数。如果不可能使P和Q相等则输出-1。否则输出一个非负整数可以执行的最大步数。输入格式一行两个整数P和Q。0PQ10^18。输出格式一个整数输入样例输出样例5 925 1025 6-1友情提示:数字0和1不是质数。解题思路题目要求通过加减质数的操作使两个非负整数P和Q相等。每次操作可以给P加任意质数或从Q减任意质数。若无法使二者相等则输出-1否则输出最大操作步数。观察若Q-P0或Q-P为1则无解当PQ时无需操作所以可执行步数为0。由于2是最小的质数只有当Q-P为偶数且≥2时最大步数为(Q-P)/2。#includebits/stdc.h using namespace std; long long int q,p; int main(){ cinpq; if((q-p)0||(q-p)1){cout-1;} else if((q-p)0){cout0;} else cout((q-p)/2); return 0; }