将数字表示为连续|集2的和（使用奇数因子）-yiteyi-C++库

给定一个数n，找出将该数表示为两个或更多连续自然数之和的方法。

null

例如：

Input : n = 15 
Output : 3
15 can be represented as:
1 + 2 + 3 + 4 + 5
4 + 5 + 6
7 + 8

Input :10
Output :2
10 can only be represented as:
1 + 2 + 3 + 4

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

我们已经在下面的帖子中讨论了一种方法。计数将一个数表示为连续数之和的方法

这里讨论了一种新的方法。假设我们讨论的是从X到Y的数字之和，即[X，X+1，…，Y-1，Y] 那么算术和就是

(Y+X)(Y-X+1)/2

如果这应该是N，那么

2N = (Y+X)(Y-X+1)

请注意，其中一个因子应为偶数，另一个因子应为奇数，因为Y-X+1和Y+X应具有相反的奇偶性，因为Y-X和Y+X具有相同的奇偶性。因为2N是偶数，我们求出N的奇数因子的个数。例如，n=15，15的所有奇数因子都是13和5，所以答案是3。

C++

                         // C++ program to count number of ways to express                       
                         // N as sum of consecutive numbers.                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
                                   
                         // returns the number of odd factors                       
                         int                                     countOddFactors(                                     long                                     long                                     n)                       
                         {                       
                                                 int                                     odd_factors = 0;                       
                                   
                                                 for                                     (                                     int                                     i = 1; 1ll * i * i <= n; i++) {                       
                                                 if                                     (n % i == 0) {                       
                                   
                                                 // If i is an odd factor and                       
                                                 // n is a perfect square                       
                                                 if                                     (1ll * i * i == n) {                       
                                                 if                                     (i & 1)                       
                                                 odd_factors++;                       
                                                 }                       
                                   
                                                 // If n is not perfect square                       
                                                 else                                     {                       
                                                 if                                     (i & 1)                       
                                                 odd_factors++;                       
                                   
                                                 int                                     factor = n / i;                       
                                                 if                                     (factor & 1)                       
                                                 odd_factors++;                       
                                                 }                       
                                                 }                       
                                                 }                       
                                                 return                                     odd_factors - 1;                       
                         }                       
                                   
                         // Driver Code                       
                         int                                     main()                       
                         {                       
                                                 // N as sum of consecutive numbers                       
                                                 long                                     long                                     int                                     N = 15;                       
                                                 cout << countOddFactors(N) << endl;                       
                                   
                                                 N = 10;                       
                                                 cout << countOddFactors(N) << endl;                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to count number                       
                         // of ways to express N as sum                       
                         // of consecutive numbers.                       
                         import                                     java.io.*;                       
                                   
                         class                                     GFG                       
                         {                       
                         // returns the number                       
                         // of odd factors                       
                         static                                     int                                     countOddFactors(                                     long                                     n)                       
                         {                       
                                                 int                                     odd_factors =                                     0                                     ;                       
                                   
                                                 for                                     (                                     int                                     i =                                     1                                     ;                                     1                                     * i * i <= n; i++)                       
                                                 {                       
                                                 if                                     (n % i ==                                     0                                     )                       
                                                 {                       
                                   
                                                 // If i is an odd factor and                       
                                                 // n is a perfect square                       
                                                 if                                     (                                     1                                     * i * i == n)                       
                                                 {                       
                                                 if                                     ((i &                                     1                                     ) ==                                     1                                     )                       
                                                 odd_factors++;                       
                                                 }                       
                                   
                                                 // If n is not                       
                                                 // perfect square                       
                                                 else                                     {                       
                                                 if                                     ((i &                                     1                                     ) ==                                     1                                     )                       
                                                 odd_factors++;                       
                                   
                                                 int                                     factor = (                                     int                                     )n / i;                       
                                                 if                                     ((factor &                                     1                                     ) ==                                     1                                     )                       
                                                 odd_factors++;                       
                                                 }                       
                                                 }                       
                                                 }                       
                                                 return                                     odd_factors -                                     1                                     ;                       
                         }                       
                                   
                         // Driver Code                       
                         public                                     static                                     void                                     main(String args[])                       
                         {                       
                                                 // N as sum of consecutive numbers                       
                                                 long                                     N =                                     15                                     ;                       
                                                 System.out.println(countOddFactors(N));                       
                                   
                                                 N =                                     10                                     ;                       
                                                 System.out.println(countOddFactors(N));                       
                         }                       
                         }                       
                                   
                         // This code is contributed by                       
                         // Manish Shaw(manishshaw1)                       

Python3

                         # Python3 program to count number                       
                         # of ways to express N as sum                       
                         # of consecutive numbers.                       
                                   
                         # returns the number                       
                         # of odd factors                       
                         def                                     countOddFactors(n) :                       
                                                 odd_factors                                     =                                     0                       
                                                 i                                     =                                     1                       
                                                 while                                     ((                                     1                                     *                                     i                                     *                                     i) <                                     =                                     n) :                       
                                                 if                                     (n                                     %                                     i                                     =                                     =                                     0                                     ) :                       
                                   
                                                 # If i is an odd factor and                       
                                                 # n is a perfect square                       
                                                 if                                     (                                     1                                     *                                     i                                     *                                     i                                     =                                     =                                     n) :                       
                                                 if                                     (i &                                     1                                     ) :                       
                                                 odd_factors                                     =                                     odd_factors                                     +                                     1                       
                                   
                                                 # If n is not perfect square                       
                                                 else                                     :                       
                                                 if                                     ((i &                                     1                                     )) :                       
                                                 odd_factors                                     =                                     odd_factors                                     +                                     1                       
                                   
                                                 factor                                     =                                     int                                     (n                                     /                                     i)                       
                                                 if                                     (factor &                                     1                                     ) :                       
                                                 odd_factors                                     =                                     odd_factors                                     +                                     1                       
                                                 i                                     =                                     i                                     +                                     1                       
                                                 return                                     odd_factors                                     -                                     1                       
                                   
                         # Driver Code                       
                                   
                         # N as sum of consecutive numbers                       
                         N                                     =                                     15                       
                         print                                     (countOddFactors(N))                       
                                   
                         N                                     =                                     10                       
                         print                                     (countOddFactors(N))                       
                                   
                         # This code is contributed by                       
                         # Manish Shaw(manishshaw1)                       

C#

                         // C# program to count number of                       
                         // ways to express N as sum of                       
                         // consecutive numbers.                       
                         using                                     System;                       
                                   
                         class                                     GFG                       
                         {                       
                                                 // returns the number                       
                                                 // of odd factors                       
                                                 static                                     int                                     countOddFactors(                                     long                                     n)                       
                                                 {                       
                                                 int                                     odd_factors = 0;                       
                                   
                                                 for                                     (                                     int                                     i = 1; 1 * i * i <= n; i++)                       
                                                 {                       
                                                 if                                     (n % i == 0)                       
                                                 {                       
                                   
                                                 // If i is an odd factor and                       
                                                 // n is a perfect square                       
                                                 if                                     (1 * i * i == n)                       
                                                 {                       
                                                 if                                     ((i & 1) == 1)                       
                                                 odd_factors++;                       
                                                 }                       
                                   
                                                 // If n is not                       
                                                 // perfect square                       
                                                 else                                     {                       
                                                 if                                     ((i & 1) == 1)                       
                                                 odd_factors++;                       
                                   
                                                 int                                     factor = (                                     int                                     )n / i;                       
                                                 if                                     ((factor & 1) == 1)                       
                                                 odd_factors++;                       
                                                 }                       
                                                 }                       
                                                 }                       
                                                 return                                     odd_factors - 1;                       
                                                 }                       
                                   
                                                 // Driver Code                       
                                                 static                                     void                                     Main()                       
                                                 {                       
                                                 // N as sum of consecutive numbers                       
                                                 long                                     N = 15;                       
                                                 Console.WriteLine(countOddFactors(N));                       
                                   
                                                 N = 10;                       
                                                 Console.WriteLine(countOddFactors(N));                       
                                                 }                       
                         }                       

PHP

                         <?php                       
                         // PHP program to count number                       
                         // of ways to express N as sum                       
                         // of consecutive numbers.                       
                                   
                         // returns the number                       
                         // of odd factors                       
                         function                                     countOddFactors(                                     $n                                     )                       
                         {                       
                                                 $odd_factors                                     = 0;                       
                                   
                                                 for                                     (                                     $i                                     = 1; 1 *                                     $i                                     *                                     $i                                     <=                                     $n                                     ;                                     $i                                     ++)                       
                                                 {                       
                                                 if                                     (                                     $n                                     %                                     $i                                     == 0)                       
                                                 {                       
                                   
                                                 // If i is an odd factor and                       
                                                 // n is a perfect square                       
                                                 if                                     (1 *                                     $i                                     *                                     $i                                     ==                                     $n                                     )                       
                                                 {                       
                                                 if                                     (                                     $i                                     & 1)                       
                                                 $odd_factors                                     ++;                       
                                                 }                       
                                   
                                                 // If n is not perfect square                       
                                                 else                                     {                       
                                                 if                                     (                                     $i                                     & 1)                       
                                                 $odd_factors                                     ++;                       
                                   
                                                 $factor                                     =                                     $n                                     /                                     $i                                     ;                       
                                                 if                                     (                                     $factor                                     & 1)                       
                                                 $odd_factors                                     ++;                       
                                                 }                       
                                                 }                       
                                                 }                       
                                                 return                                     $odd_factors                                     - 1;                       
                         }                       
                                   
                         // Driver Code                       
                                   
                         // N as sum of consecutive numbers                       
                         $N                                     = 15;                       
                         echo                                     (countOddFactors(                                     $N                                     ) . (                                     ""                                     ));                       
                                   
                         $N                                     = 10;                       
                         echo                                     (countOddFactors(                                     $N                                     ));                       
                                   
                         // This code is contributed by                       
                         // Manish Shaw(manishshaw1)                       
                         ?>                       

输出：

3
1

这个程序的时间复杂度是O（N^0.5）。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章