洛谷 P1134 阶乘问题

一开始只保留最后一位，交上去29

#include<cstdio>

#include<cmath>

#include<algorithm>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

#define _for(i, a, b) for(int i = (a); i <= (b); i++)

using namespace std;

int main()

{

	int n, ans = 1;

	scanf("%d", &n);

	_for(i, 2, n)

	{

		ans *= i;

		while(ans % 10== 0) ans /= 10;

		ans %= 10;

   }

   printf("%d\n", ans % 10);

   return 0;

}

然后通过数据发现

然后我就把真正的数和我保留最后一位的数比较一下，发现有一组数据答案有问题

i = 14 sum = 87178291200 ans = 2

i = 15 sum = 130767436800 ans = 3

这组数据是关键

如果按照最后一位的话，2 * 15 = 30, 取3

但是我们把sum手算乘上15会发现

87178291200

15

----------------

…… 60

……2

-----------------

……80

这里可以看到，影响到末尾的位的是后两位，而不仅仅是最后一位

所以以此类推，乘数最大为10的8次方方级别，所以我就只需要存

去0情况下的最后8位数就好了。8位数乘8位数int会炸，所以开longlong

#include<cstdio>

#include<cmath>

#include<algorithm>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

#define _for(i, a, b) for(int i = (a); i <= (b); i++)

using namespace std;

typedef long long ll;

const int base = 1e8;

int main()

{

	int n; ll ans = 1;

	scanf("%d", &n);

	_for(i, 2, n)

	{

		ans *= i;

		while(ans % 10== 0) ans /= 10;

		ans %= base;

   }

   printf("%lld\n", ans % 10);

   return 0;

}

巴特西

洛谷 P1134 阶乘问题

最新文章

热门文章