PAT(A)1096 Consecutive Factors (20 分)

Sample Input:

630

Sample Output:

3
5*6*7

思路: 找出最长连续的因子，注意循环到sqrt(n)即可，就像判断素数，然后每次找到因子就判断后面是不是连续，然后计数，记录开始位置，最后得到最大的连续个数，及开始位置，输出即可。

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;

typedef long long ll;

int main()
{
	ll n;
	scanf("%lld", &n);

	ll a = (ll)sqrt(n * 1.0);

	ll len = -1, first = 0;

	for (ll i = 2; i <= a; ++i)
	{
		ll t = 1;
		ll j = i;

		while (1)
		{
			t *= j;
			if (n % t != 0)
				break;
			if (j - i + 1 > len)
			{
				len = j - i + 1;
				first = i;
			}
			j++;
		}
	}

	if (len == -1)
	{
		printf("1\n");
		printf("%lld", n);
		return 0;
	}

	//int ans = first;

	printf("%lld\n", len);

	printf("%lld", first);
	for (ll i = 1; i < len; ++i)
	{
		printf("*%lld", first + i);
	}

	return 0;
}