题面

题目描述 Description

 成为一个怎样的人，是日复一日的攀登，是对内心深处渴望千万次的回应。

小咸鱼是很可爱的女孩子。 小咸鱼渴望成为一只优秀的咸鱼。作为一只有梦想的咸鱼，小咸鱼每天都在 为实现梦想而努力着。 有一天，小咸鱼在刷题的时候遇到了一道题目：求n的阶乘%998244353。有 着丰富的刷题经验的小咸鱼很快地就写出了这道套路题。 但是，作为一道高质量的题目，这道题的下面还写着一个奇怪的变式：求n的 阶乘末尾第一个非零数字和阶乘末尾零的个数。 小咸鱼冷静分析了片刻，写下了自己的解法。当她企图根据标准答案来判断 自己的解法是否正确的时候，她惊讶地发现，答案竟然只写了一个略。 无奈的小咸鱼只好找到了你，请你解出问题来帮忙验证一下她的解法是否正 确。

输入格式 Input Format

第一行，一个整数T，表示数据组数。 接下来T行，每行一个整数n，表示这组数据要求n的阶乘末尾第一个非零数 字和阶乘末尾零的个数。

输出格式 Output Format

共T行，每行两个整数，分别表示这组数据中n的阶乘末尾第一个非零数字和 阶乘末尾零的个数。

样例输入 Sample Input

2
5
10

样例输出 Sample Output

2 1
8 2

数据范围与约定 Constraints

本题有设置部分分，对于每个测试点，如果你每行的第一个数都和标准输出 一样，你将会得到7分；如果你每行的第二个数都和标准输出一样，你将会得到 3分。 对于所有数据，满足1 ≤ T ≤ 10^5,0 ≤ n ≤ 10^18。

题解

前言：

这道是神犇jyt出的套题的第三题，考场上再码第二的数据结构，就没有看这题（结果数据结构还打飞了）。这题看似是道数学题，实际上也的确是道数学题。但它的思路十分诡异（其实是我太弱，所以才理解好久），我将思路整理好，才来写这篇题解

先考虑第二问，发现十分简单（其实对我来说并不简单）。第二问，求零的个数，其实就是求n！中10这个因子的个数，我们将10看做2*5，发现，只要统计5的个数即可，因为n！中2这个因子显然多于5。那么第二问的答案就为

$ans=\frac{n}{5^1}+\frac{n}{5^2}+\frac{n}{5^3}+……+\frac{n}{5^p}$

这是数论中的基础（在lzx神犇看来是这样的）。 接下来考虑第一问。我们设第二问的答案为k $10^k*m=n!$ 那显然m的最后一位就是第一问答案了。因为m一定为偶数（它包含了若干个2），所以答案一定是2，4，6，8中的一个。然后有一个显然的关系$2^k*m\equiv x(mod 5)$（嗯，很显然）。然后在mod 5意义下$2^k*m$可以背看做若干个$4!*（一些奇怪的东西）$。$4!= 24 mod 5 = 4$，所以就变成了$4^t*(一些奇怪的东西)$，然后考虑求t， 我将在mod 5意义下的n！的前部分列了出来即： （12341）（12342）（12343）（12344）…… 然后，观察规律，惊讶地发现t==k（嗯，就是这么玄学），就是有k个4！。接下来考虑那一些奇怪的部分，观察上式，我以5为循环节在计算，每个循环节是一个4！（除去最后那个，那个要若干个小循环节和起来一起算）。没错，就跟mod 5一样，我们接下来要考虑剩余个数如果的数不足5个改怎么办：很简单，如果剩1个就是1；2个就是2！就是2；3个就是123=6，但是在mod 5意义就是1；如果是4个，就是*4！=*24 mod 5=4。综上我们可以得出这样的式子： $2^k*m\equiv 4^k*4^{las4}*2^{las2}（mod 5）$(las4表示余下的4！的个数，las2同理) 整理一下$m\equiv 2^{k+las4*2+las2} (mod 5)$ 然后2^4=16 mod 5=1;所以只要判断（k+las42+las2）mod 4的值即可，在{2，4，6，8}中选出一个。

代码很短，单想到做到真还不容易啊。

#include<cstdio>
#define ll long long
int T;
ll n,m,k,las2,las4;
const int a[4]={6,2,4,8};
int main(){
	scanf("%d",&T);
	while(T--){
		las2=las4=k=0;
		scanf("%lld",&n);
		for(ll i=n;i;i/=5){
			k+=i/5;
			las2+=(i%5==2);//余下的2！个数 
			las4+=(i%5==4);//余下的4！个数 
		}
		printf("%d %lld\n",a[(las2+las4*2+k)%4],k);
	}
	return 0;
}

讲的不好，还请指正，不胜感激。