题意描述

求 \(n!\) 在 \(b\) 进制表示下的第一位非 \(0\) 位的数字。

算法分析

闲话

忙人自动略过

之前做过一道 \(10\) 进制表示下的题目，感觉差不多。

一开始没什么思路，就随手打了个暴力进去，结果竟然 AC 了。（只能说数据水）

n=read(),b=read();

for(int i=2;i<=n;i++){

    f*=i;

    while(f%b==0)

        f/=b;

    f%=b;

}

开开心心交给 GY，结果 \(2\) 分钟之后被 Hack 了。

对于 15 10，显然答案为 \(8\)，但是程序给出的结果为 \(3\)。

被 Hack 的结果是我只记录了末尾 \(1\) 位的数值，由于 \(14!\) 的末尾为 \(2\)，所以 \((2\times 15)\ mod\ 10=3\)。

所以对于十进制来说，记录末尾 \(7\) 位就不会有问题了，但是对于 \(b\) 进制来说却远远不够，只能另寻他路。

下面是正解。

正解

终于要 BB 正解了

让我们假设 \(n!\) 的 \(b\) 进制表示的末尾并没有 \(0\)（即 \(n!\ mod\ b\neq 0\)），那么答案只要保留一位不断 \(mod\ b\) 即可。

虽然显然几乎不可能有这种情况发生，但是我们可以构造这种情况。

倘若我们把 \(n!\) 表示为 \(b^k\times a\)，那么我们只需要求 \(a\) 的 \(b\) 进制表示的第一位即可（因为 \(a\ mod \ b\neq 0\)）。

实现方法是将 \(b\) 质因数分解，然后将 \(n!\) 都质因数分解，将 \(b\) 的质因子减去殆尽即可。

具体看代码吧。

代码实现

#include<cstdio>

#include<cstring>

#include<iostream>

#include<cmath>

#include<algorithm>

#define N 20

using namespace std;

int n,b,tot[N],num[N];

int pri[N],cnt=0;

int prime[N]={0,2,3,5,7,11,13,17,19,23,29};

//B 的质因子只有这 10 中可能。

int read(){

	int x=0,f=1;char c=getchar();

	while(c<'0' || c>'9') f=(c=='-')?-1:1,c=getchar();

	while(c>='0' && c<='9') x=x*10+c-48,c=getchar();

	return x*f;

}

int main(){

	n=read(),b=read();

	memset(tot,0,sizeof(tot));

	memset(num,0,sizeof(num));

	int bb=b;

	for(int i=1;i<=10;i++){

		if(bb%prime[i]!=0) continue;

		pri[++cnt]=prime[i];//记录 B 的质因子的种类。

		while(bb%prime[i]==0) bb/=prime[i],++num[cnt]; //记录 B 的质因子个数。

	}

	int ans=1;

	for(int i=1;i<=n;i++){

		int now=i;

		for(int j=1;j<=cnt;j++)

			while(now%pri[j]==0)

				now/=pri[j],++tot[j];//记录其中 B 的质因子的个数。

		ans=(ans*now)%b;//剩余部分直接计算即可。

	}

	int z=0x3f3f3f3f;

	for(int i=1;i<=cnt;i++)

		z=min(z,tot[i]/num[i]);

	for(int i=1;i<=cnt;i++)

		tot[i]-=num[i]*z;//将 B 的质因子减去殆尽。

	for(int i=1;i<=cnt;i++)

		for(int j=1;j<=tot[i];j++)

			ans=(ans*pri[i])%b;//剩下的直接乘即可。

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

	return 0;

}

完结撒❀。

巴特西

【USACO】Cow Brainiacs

题意描述

算法分析

闲话

正解

代码实现

最新文章

热门文章