搜索
首页后端开发C++将阶乘n表示为连续数字的和

将阶乘n表示为连续数字的和

我们将讨论两种方法来找出如何将数字的阶乘表示为连续数字的总和。第一种方法是直接而简单的方法,而在另一种方法中,我们使用算术级数的概念来使其在占用的时间和空间方面不那么复杂。

问题陈述

给定一个数字,我们需要找出可以将数字的阶乘表示为连续自然数之和的方法。

这涉及两个不同的功能 -

  • 求数字的阶乘。

  • 找出可以将数字表示为连续自然数之和的方法数。

示例1

Given : Number = 3
Result: 1

众所周知,3 的阶乘是 6,可以写成 1+2+3,因此我们的答案是:1 种方式。

示例2

Given: Number = 4
Result: 1

众所周知,4 的阶乘是 24,可以写成 7+8+9,因此我们的答案是:1 种方式。

方法 1

这是一种简单的方法,我们首先找出数字的阶乘,然后计算可以将其表示为连续自然数之和的方法数。该方法是将阶乘表示为算术长度 len+1 的级数为 -

Factorial of Number = p + (p+1) + (p+2) + … + (p+len) 
So, p = (Number- len*(len+1)/2)/(len+1) 
We will check for the values of len from 1 to len*(len+1)/2<Number

当我们获得 len 为正整数时,我们将其视为一个解。

示例

在下面的示例中,我们尝试找出将数字的阶乘表示为连续数字之和的方法的数量。

#include <bits/stdc++.h>
using namespace std;

// code for obtaining number of possible solutions
long int Number_of_solutions(long int NUMBER){
   long int counter = 0;
   for (long int len = 1; len * (len + 1) < 2 * NUMBER; len++) {
      double p = (1.0 * NUMBER - (len * (len + 1)) / 2) / (len + 1);
      if (p - (int)p == 0.0)
      counter++;
   }
   return counter;
}

// main program goes here
int main(){
   long int NUMBER = 15;
   cout << "Number of ways to write 15 as a sum of consecutive numbers: ";
   cout << Number_of_solutions(NUMBER) << endl;
   NUMBER = 10;
   cout << "Number of ways to write 10 as a sum of consecutive numbers: ";
   cout << Number_of_solutions(NUMBER) << endl;
   return 0;
}

输出

当您运行上述 C++ 程序时,它将产生以下输出 -

Number of ways to write 15 as a sum of consecutive numbers: 3 
Number of ways to write 10 as a sum of consecutive numbers: 1

方法2:优化方法

这是一个更好的方法;我们上面看到的方法会导致溢出。

从数字 p 开始的 len 个连续数字的总和可以写为 -

sum = (p+1) + (p+2) + (p+3) … + (p+len) 
Hence, sum = (len*(len + 2*p + 1))/2

因为 sum 也等于 Number!。

我们可以写

2*Number! = (len*(len + 2*p + 1))

这里,我们将计算所有 (len, (len + 2*p + 1)) 对,而不是计算所有 (len, p) 对。这意味着我们将计算所有有序的 pf (A, B),其中 AB=2*Number!并且 A

这意味着我们正在寻找 2*Number 的奇数约数!这也是 Number 的奇数除数!

要计算除数的数量!,我们必须计算素数在因式分解中的幂,除数的数量为 (f1 + 1)*(f2 + 1)* … *(fn + 1)。

我们将使用勒让德公式计算素数在数字阶乘中的最大幂。

示例

下面给出了这种方法的代码 -

#include <bits/stdc++.h>
using namespace std;
#define maximum 5002
vector<int> v;
void sieve(){
   bool Is_the_number_prime[maximum];
   memset (Is_the_number_prime, true, sizeof(Is_the_number_prime) );
   for (int prime = 2; prime * prime < maximum; prime++) {
      if (Is_the_number_prime[prime] == true) {
         for (int iterator = prime * 2; iterator < maximum; iterator += prime)
         Is_the_number_prime[iterator] = false;
      }
   }
   for (int prime = 2; prime < maximum; prime++)
   if (Is_the_number_prime[prime])
   v.push_back(prime);
}
long long int calculate_largest_power(long long int a, long long int b){
   long long int c = 0;
   long long int x = b;
   while (a >= x) {
      c += (a / x);
      x *= b;
   }
   return c;
}
long long int modular_mult(long long int a,
long long int b,
long long int m){
   long long int result = 0;
   a = a % m;
   while (b > 0) {
      if (b % 2 == 1)
      result = (result + a) % m;
      a = (a * 2) % m;
      b /= 2;
   }
   return result % m;
}
long long int no_of_ways(long long int n,
long long int m){
   long long int answer = 1;
   for (int iterator = 1; iterator < v.size(); iterator++) {
      long long int powers = calculate_largest_power(n, v[iterator]);
      if (powers == 0)
      break;
      answer = modular_mult(answer, powers + 1, m)%m;
   }
   if (((answer - 1) % m) < 0)
   return (answer - 1 + m) ;
   else
   return (answer - 1) ;
}
int main(){
   sieve();
   long long int n = 4, m = 7;
   cout << "Number of solutions after performing modulo with 7 is " <<no_of_ways(n, m);
   return 0;
}

输出

当运行上面的C++程序时,它将产生以下输出 -

Number of solutions after performing modulo with 7 is 1.

结论

在本文中,我们讨论了两种不同的方法来找出数字,将数字的阶乘表示为连续自然数之和。

以上是将阶乘n表示为连续数字的和的详细内容。更多信息请关注PHP中文网其他相关文章!

声明
本文转载于:tutorialspoint。如有侵权,请联系admin@php.cn删除
C在现代世界中:应用和行业C在现代世界中:应用和行业Apr 23, 2025 am 12:10 AM

C 在现代世界中的应用广泛且重要。1)在游戏开发中,C 因其高性能和多态性被广泛使用,如UnrealEngine和Unity。2)在金融交易系统中,C 的低延迟和高吞吐量使其成为首选,适用于高频交易和实时数据分析。

C XML库:比较和对比选项C XML库:比较和对比选项Apr 22, 2025 am 12:05 AM

C 中有四种常用的XML库:TinyXML-2、PugiXML、Xerces-C 和RapidXML。1.TinyXML-2适合资源有限的环境,轻量但功能有限。2.PugiXML快速且支持XPath查询,适用于复杂XML结构。3.Xerces-C 功能强大,支持DOM和SAX解析,适用于复杂处理。4.RapidXML专注于性能,解析速度极快,但不支持XPath查询。

C和XML:探索关系和支持C和XML:探索关系和支持Apr 21, 2025 am 12:02 AM

C 通过第三方库(如TinyXML、Pugixml、Xerces-C )与XML交互。1)使用库解析XML文件,将其转换为C 可处理的数据结构。2)生成XML时,将C 数据结构转换为XML格式。3)在实际应用中,XML常用于配置文件和数据交换,提升开发效率。

C#vs. C:了解关键差异和相似之处C#vs. C:了解关键差异和相似之处Apr 20, 2025 am 12:03 AM

C#和C 的主要区别在于语法、性能和应用场景。1)C#语法更简洁,支持垃圾回收,适用于.NET框架开发。2)C 性能更高,需手动管理内存,常用于系统编程和游戏开发。

C#与C:历史,进化和未来前景C#与C:历史,进化和未来前景Apr 19, 2025 am 12:07 AM

C#和C 的历史与演变各有特色,未来前景也不同。1.C 由BjarneStroustrup在1983年发明,旨在将面向对象编程引入C语言,其演变历程包括多次标准化,如C 11引入auto关键字和lambda表达式,C 20引入概念和协程,未来将专注于性能和系统级编程。2.C#由微软在2000年发布,结合C 和Java的优点,其演变注重简洁性和生产力,如C#2.0引入泛型,C#5.0引入异步编程,未来将专注于开发者的生产力和云计算。

C#vs. C:学习曲线和开发人员的经验C#vs. C:学习曲线和开发人员的经验Apr 18, 2025 am 12:13 AM

C#和C 的学习曲线和开发者体验有显着差异。 1)C#的学习曲线较平缓,适合快速开发和企业级应用。 2)C 的学习曲线较陡峭,适用于高性能和低级控制的场景。

C#vs. C:面向对象的编程和功能C#vs. C:面向对象的编程和功能Apr 17, 2025 am 12:02 AM

C#和C 在面向对象编程(OOP)中的实现方式和特性上有显着差异。 1)C#的类定义和语法更为简洁,支持如LINQ等高级特性。 2)C 提供更细粒度的控制,适用于系统编程和高性能需求。两者各有优势,选择应基于具体应用场景。

从XML到C:数据转换和操纵从XML到C:数据转换和操纵Apr 16, 2025 am 12:08 AM

从XML转换到C 并进行数据操作可以通过以下步骤实现:1)使用tinyxml2库解析XML文件,2)将数据映射到C 的数据结构中,3)使用C 标准库如std::vector进行数据操作。通过这些步骤,可以高效地处理和操作从XML转换过来的数据。

See all articles

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

Video Face Swap

Video Face Swap

使用我们完全免费的人工智能换脸工具轻松在任何视频中换脸!

热工具

记事本++7.3.1

记事本++7.3.1

好用且免费的代码编辑器

DVWA

DVWA

Damn Vulnerable Web App (DVWA) 是一个PHP/MySQL的Web应用程序,非常容易受到攻击。它的主要目标是成为安全专业人员在合法环境中测试自己的技能和工具的辅助工具,帮助Web开发人员更好地理解保护Web应用程序的过程,并帮助教师/学生在课堂环境中教授/学习Web应用程序安全。DVWA的目标是通过简单直接的界面练习一些最常见的Web漏洞,难度各不相同。请注意,该软件中

螳螂BT

螳螂BT

Mantis是一个易于部署的基于Web的缺陷跟踪工具,用于帮助产品缺陷跟踪。它需要PHP、MySQL和一个Web服务器。请查看我们的演示和托管服务。

SublimeText3汉化版

SublimeText3汉化版

中文版,非常好用

mPDF

mPDF

mPDF是一个PHP库,可以从UTF-8编码的HTML生成PDF文件。原作者Ian Back编写mPDF以从他的网站上“即时”输出PDF文件,并处理不同的语言。与原始脚本如HTML2FPDF相比,它的速度较慢,并且在使用Unicode字体时生成的文件较大,但支持CSS样式等,并进行了大量增强。支持几乎所有语言,包括RTL(阿拉伯语和希伯来语)和CJK(中日韩)。支持嵌套的块级元素(如P、DIV),