蓝桥杯算法提高VIP-拿糖果 （C语言代码）（思路）

题目描述：

妈妈给小B买了N块糖！但是她不允许小B直接吃掉。
假设当前有M块糖，小B每次可以拿P块糖，其中P是M的一个不大于根号下M的质因数。这时，妈妈就会在小B拿了P块糖以后再从糖堆里拿走P块糖。然后小B就可以接着拿糖。
现在小B希望知道最多可以拿多少糖。

解题思路:

1、除了最后剩下的数目为质数的糖果，可获得其余糖果数的一半。所以剩下的越少，小B获得的越多。即目标为使剩余糖果书尽量少。

2、分两种情况：（1）糖果能分完，剩余0；（2）不能分完，剩余数目尽量少。

3、能分完的条件：

    m=2*p

    p<=sqrt(m)，即p*p<=m

    解得p = 2，m = 4

    即某次剩余4个糖果时可以分完，小B获得n/2个。

    进一步，某次糖果数m为4的倍数，每次都分2个，则必最终m=4。如m = a*4，让p=2，则下一次m=(a-1)*4。

    再进一步，m如果能分解为m=2*a*b，即使m不是4的倍数，如a、b都是奇数，同样能分完。令p=a，下一个m₁=2*a*b-2*a=2*a*(b-1)，此时m₁就成了4的倍数。

    综上可得能分完时n的限制条件：n和n/2均不是质数。

4、不能分完如何处理：

    不能分完时要使剩下的数量尽量少。

    如n=3*5*7=105，此时每次取3个，即p=3，则最终必然剩余3个。当p=a时，总有m=a*(b-2)，最后一次分完后只剩下a个，所以要尽量使每次分的个数p为最小质因数。

    即不能分完时，应每次分m的最小质因数个糖。

    如n=5*5时，p=5

    m₁=25-2*5=15=3*5，p₁=3；

    m₂=15-2*3=9=3*3，p₂=3；

    m₃=9-2*3=3

    剩余3个，小B获得（25-3）/2=11个

参考代码:

1、判断 n 在 m 以内有没有质因数

int prime(int n,int m) {
    	int i;
    	int t = 0;
    	for (i=2;i<m;i++) {
        	if (n%i==0) {
            	t = i;
            	break;
        	}
    	}
    	return t;
}

2、将 m=a*b 进行递归，每次取m的最小质因数a个糖

int f(int a, int b) {
	if (b<2) {
		return a*b;    //返回最终剩余糖数
	}
	int t = prime(b,a);    //如果m有比a小的质因数，a取最小质因数的值，继续递归
	if (t) {
		a = t;
		b = a*b/t;
	}
	f(a,b-2);
}

3、主程序

int main()
{
	int n,m,i;
	scanf("%d",&n);
	m = n;
	
	if (n%2==0 && prime(n/2,n/4+1)) {	//判断能否分完，分完标志为其中一次m为4的倍数 
		m = 0;
	}
	else {
		for (i=2;i<n/2;i++) {		//分不完时，每次去最小质因数个糖
			if (n%i==0) {
				break;
			}
		}
		m = f(i,n/i);
	}

	printf("%d",(n-m)/2);
	return 0;
}