当前位置: 代码迷 >> 综合 >> SSLOJ 1490.阶乘(fact)
  详细解决方案

SSLOJ 1490.阶乘(fact)

热度:81   发布时间:2024-02-12 03:31:11.0

SSLOJ 1490.阶乘

  • 题目
    • 题目描述
    • 输入
    • 输出
    • 样例
    • 说明
  • 思路
    • 质因数分解
      • 算术基本定理
      • 试除法
    • 阶乘分解
  • 反思
  • 代码

题目

题目描述

在这里插入图片描述

输入

第一行有一个正整数T,表示测试数据的组数。
接下来的T行,每行输入两个十进制整数n和base。

输出

对于每组数据,输出一个十进制整数,表示在base进制下,n!结尾的零的个数。

样例

输入样例
2
10 10
10 2
输出样例

2

8

说明

对于20%的数据,n<=20,base<=16

对于50%的数据,n<=109,base<=105

对于100%的数据,1<=T<=50,0<=n<=10 ^ 18,2<=base<=10 ^ 12

思路

base进制下末尾为0,意味着什么呢?
十进制下10,末尾加一个0
二进制下
2,末尾也加一个0
是不是发现了什么
没错,想想短除法转化进制
仔细思考下(下面是(14)10转二进制):
在这里插入图片描述

剩下的怎么处理,看完就明白了
以下摘自《算法竞赛进阶指南(李煜东 著)》P137~138

质因数分解

算术基本定理

任何一个大于1的正整数都能唯一分解为有限个质数的乘积,可写作:N= p1c1 *p2c2 * … * pmcm
其中ci都是正整数,pi都是质数,且满足P1<P2<…<Pm。

试除法

结合质数判定的“试除法”和质数筛选的“Eratosthenes筛法”,我们可以扫描2~floor(sqrt(n))的每个数d,若d能整除N,则从N中除掉所有的因子d,同时累计除去的d的个数。
因为一个合数的因子一定在扫描到这个合数之前就从N中被除掉了,所以在上述过程中能整除N的一定是质数。最终就得到了质因数分解的结果,易知时间复杂度为0(VN)。
特别地,若N没有被任何2~VN的数整除,则N是质数,无需分解。

阶乘分解

给定整数N(1≤N≤106),试把阶乘N!分解质因数,按照算术基本定理的形式输出分解结果中的pi和ci即可。
若把1 ~ N每个数分别分解质因数,再把结果合并,时间复杂度过高,为0(Nsqrt(N)).显然,N!的每个质因子都不会超过N,我们可以先筛选出1~N的每个质数p,然后考虑阶乘N!中一共包含多少个质因子p。
N!中质因子p的个数就等于1 ~ N每个数包含质因子p的个数之和。在1~N中,p的倍数,即至少包含1个质因子p的显然有[N/p]个。而p2的倍数,即至少包含2个质因子p的有[N/p2]个。不过其中的1个质因子已经在[N/p]里统计过,所以只需要再统计第2个质因子,即累加上[N/p2],而不是2*[N/p2]。
综上所述,N!中质因子p的个数为:
对于每个p,只需要O(logN)的时间计算上述和式。故对整个N!分解质因数的时间复杂度为O(NlogN)。

反思

这题交了很多次都没过,都是些细节问题,以后要多注意,多思考细节

代码

#include <iostream>
#include <cstdio>
#define ll long long
using namespace std;
ll n , base;
ll cnt;
int main(){int T;cin >>T;while(T--){cin >> n >> base;ll minn = (1ll << 60);for(ll i = 2 ; i * i <= base ; i++){//错误1:当时i没开longlong,以为不用,但是i*i会爆掉if(base % i == 0){cnt = 0;while(base % i == 0)base /= i , cnt++;ll sum = 0;for(ll j = i ; j <= n ; j *= i){sum += n / j;if(j > n / i)break;
//错误2:当时没注意这点,原因是当j非常接近n时,再乘以i也会出事(n到10^18时已经接近longlong极限),需要提前判断,当然,其他博客也有其他更简单的写法}sum /= cnt;if(sum < minn)minn = sum;}}if(base > 1){ll sum = 0;for(ll j = base ; j <= n ; j *= base){sum += n / j;if(j > n / base)break;}if(sum < minn)minn = sum;}cout << minn << endl;}return 0;
}

链接:其他写法https://blog.csdn.net/qq_43412506/article/details/87008006