資料結構
網路
關係資料庫管理系統 (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 次瀏覽
