首页 > 其他分享 >阶乘质因数分解

阶乘质因数分解

时间:2024-11-01 22:31:05浏览次数:1  
标签:lfloor frac 因数分解 int 质数 rfloor 阶乘 log

\(1 \leq n \leq 10^6\), 唯一分解(质因数分解) \(n!\),输出 \(p_i,c_i\)。

阶乘分解 AcWing197

思路

前置知识:线性筛 (质数判定的算法4)。

显然 \(n!\) 的每个质因子都小于等于 \(n\)。

因为 \(n! = n(n-1)(n-2)(n-3)\cdots 3 \cdot 2 \cdot 1\),所以质数 \(p\) 在 \(n!\) 出现的次数为 \(p\) 在 \(1\sim n\) 出现的次数。

对于 \(i=1,2,3\dots n\):

对于 \(p\):若有 \(p|i\),则 \(p\) 出现次数+1

对于 \(p^2\):若有 \(p^2|i\),则 \(p\) 出现次数 +1,而不是 +2,因为其中一个 \(p\) 在 \(p|i\) 时被统计了。

对于 \(p^3\):若有 \(p^3|i\),则 \(p\) 出现次数 +1,而不是 +3,因为其中一个 \(p\) 在 \(p|i\) 时被统计了,另一个 \(p\) 在 \(p^2|i\) 时被统计了。

...

则 \(p\) 在 \(n!\) 中出现的次数为 \(\lfloor\frac{n}{p}\rfloor + \lfloor\frac{n}{p^2}\rfloor + \lfloor\frac{n}{p^3}\rfloor + \cdots + \lfloor\frac{n}{p^{\lfloor\log_p{n}\rfloor}}\rfloor = \sum\limits_{p^k\leq n}{\lfloor\frac{n}{p^k}\rfloor}\)。

综上有以下步骤:

  • 线性筛求 \(1 \sim n\) 内的质数。\(O(n)\)
  • 遍历 \(1 \sim n\) 内的质数,找出质数\(p\),\(p|n\)。\(O(\pi(n))=O(\frac{n}{\log n})\)
    • 对于质数 \(p\),求出在 \(n!\) 中出现的次数。\(O(\log n)\)

\(\pi(x)\) 是小于等于 \(x\) 的质数个数,约等于 \(\frac{n}{\log n}\)

综上时间复杂度为 \(O(n + \frac{n}{\log n} \cdot \log n) = O(n)\)。

代码实现

int n;
long long v[N];
::std::vector<int> ps;
int main() {
	scanf("%d", &n);

	/* 线性筛 */
	for(int i = 2; i <= n; i++)
	{
		if(!v[i])
			v[i] = i, ps.push_back(i);
		for(int j : ps)
			if(v[i] < j || j > n / i) break;
			else v[i * j] = j;
	}

	for(int i : ps)
	{
		ll p = i;
		int c = 0;
		while(p <= n)
		{
			c += n / p;
			p *= i;
		}
		printf("%d %d\n", i, c);
	}
	return 0;
}

标签:lfloor,frac,因数分解,int,质数,rfloor,阶乘,log
From: https://www.cnblogs.com/kuailedetongnian/p/18521395

相关文章

  • 《练习题011:阶乘-递归-反向输出-排序-逆序(共9种)》
    《目录》01:阶乘求和02:递归求阶乘03:递归输出04:反向输出05:反向输出II06:设置输出颜色07:算素数08:排序09:逆序列表01:阶乘求和题目求1+2!+3!+…+20!的和。程序分析1+2!+3!+…+20!=1+2(1+3(1+4(…20(1))))res=1foriinrange(20,1,-1):res=i*res+1......
  • 100种算法【Python版】第14篇——Pollard‘s Rho 质因数分解算法
    本文目录1基本原理2算法步骤3数学示例4python代码1基本原理Pollard’sRho算法是由约翰·波拉德(JohnPollard)于1975年提出的一种用于整数因数分解的概率算法。它以高效性和实现简洁著称。核心原理伪随机序列生成:利用一个简单的迭代函数生成一个伪随机......
  • JSP网页计算阶乘
    <%@pagelanguage="java"contentType="text/html;charset=UTF-8"pageEncoding="UTF-8"%><!DOCTYPEhtml><html><head><metacharset="UTF-8"><title>阶乘计算</title></head......
  • 算法设计与分析(阶乘
    目录计算阶乘的递归函数阶乘函数的实现代码解释递归的优点与缺点优点:缺点:小结:计算阶乘的递归函数在编程中,阶乘是一个常见的概念,它表示从1乘到某个给定数n的所有整数的乘积。例如,5的阶乘(记作5!)是12345=120。这里,我们将通过C++语言实现一个递归函数来计算任意非负整数的阶乘。递归......
  • 打卡信奥刷题(774)用Scratch图形化工具信P5739[普及组/提高组] 【深基7.例7】计算阶乘
    【深基7.例7】计算阶乘题目描述求n!n!n!,也就是1×......
  • PTA 6-10 阶乘计算升级版(详讲)
    6-10阶乘计算升级版-基础编程题目集(pintia.cn)https://pintia.cn/problem-sets/14/exam/problems/type/6?problemSetProblemId=742&page=0首先这道题不能用我们之前学过的阶乘计算方法来解决,比如下面这段代码就无法通过全部的样例voidPrint_Factorial(constintN)......
  • 从阶乘幂到斯特林数(未完成)
    OI-wiki抄一点,《具体数学》抄一点,抄抄你的,抄抄他的斯特林数-OIWiki(oi-wiki.org)斯特林数及斯特林反演-y2823774827y-博客园(cnblogs.com)阶乘幂我们记下降阶乘幂\[x^{\underline{n}}=\dfrac{x!}{(x-n)!}=\prod_{k=0}^{n-1}(x-k)\]上升阶乘幂\[x^{\overline{n}}......
  • 阶乘后的零
    题目描述:给定一个整数n,返回n!结果中尾随零的数量。提示n!=n*(n-1)*(n-2)*...*3*2*1示例1:输入:n=3输出:0解释:3!=6,不含尾随0示例2:输入:n=5输出:1解释:5!=120,有一个尾随0示例3:输入:n=0输出:0提示:0<=n<=104进阶:你可以设计并实现对数......
  • 累加n次阶乘分之一
    请编写函数fun,其功能是:计算并输出下列多项式的值:例如,在主函数中从键盘给n输入15,则输出为:s=2.718282注意:要求n的值大于1但不大于100。#include<stdio.h>#pragmawarning(disable:4996)doublefun(intn){ inti=0; intj=1; doublesum=1; for(i=1;i<=n;i+......
  • c++质因数分解
    质因数分解,最先想到了遍历1-n,找出既是质数也是因数的数。需要用到判断质数函数、while循环,复杂度三次方以上了。#include<iostream>usingnamespacestd;boolzs(intn){ for(inti=2;i<=n/2;i++){ if(n%i==0){ return1; } } return0;}intmai......