数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学将阶乘 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) 对。这意味着我们将计算所有有序对 (A, B)，其中 AB=2*Number! 且 A< B，并且 A 和 B 的奇偶性不同，这意味着如果 len 是奇数，则 (len + 2*p + 1) 是偶数；如果 len 是偶数，则 (len + 2*p + 1) 是奇数。
这意味着我们正在寻找 2*Number! 的奇数约数，这也是 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.
结论
在本文中，我们讨论了两种不同的方法来找出可以将一个数的阶乘表示为连续自然数之和的方法数量。
244 次浏览
