leecode | 829连续整数求和

发布时间:2024年01月05日

给一个整数n 求连续整数的和等于n 的个数
这道题 是一个数论的思想

解决思路: 数必须是连续的,可以转化成一个通用的公式,以101为例做一般性推导,: 101 = 101 = 50 + 51 = 24 + 25 + 26 + 27 = 24 * 4 + 6 = a *n + (n - 1)*n/2

归纳出一般性结论: y = a * n + (n - 1) * n / 2 ==> a = y/n - (n - 1) / 2 ==> 猜想:a是整数才能匹配

以y=101为例 a = 101/n - (n - 1) / 2 (n - 1) / 2的小数位为0.5或0,当n > 2时,101/n小数位肯定不为0或者0.5,所以a = 101/n - (n - 1) / 2肯定>不为整数

问题可以转化为求n的值

推演: 示例1: 以15为例 15 = a * n + (n - 1) * n / 2 a = 15/n - (n - 1) / 2

当n=1: a = 15 匹配 15

当n=2: a*2 + 1 = 15 a = 7 匹配 7,8

当n=3: a*3 + 3 = 15 a = 4 匹配 4,5,6

当n=4: a*4 + 6 = 15 a = 9/4 不能除尽 不匹配

当n=5: a*5 + 10 = 15 a = 1 匹配 1,2,3,4,5

a = 1 不大于1,匹配结束, 匹配结果为n=3组

class Solution {
public:
    int consecutiveNumbersSum(int n) {
        //(a, k)
        // (a + a + k - 1)*k/2 = n
        //2a = 2n/k-k+1 ==> 
        //2a = 2n/k -k + 1 >= 2 ==> 2n/k >= k+1 <==> 2n/k > k
        //那么 就在 [1, 2n^1/2) 的范围去枚举 k 
        // 如果k  是2n约数,再结合 (2a+k-1)*k = 2n 就可以验证a合法
        //枚举k 就好, k 必是2n的约数,并且为 较小 的约数
        //经过推论 ,满足上面的不等式  接着两个条件 就把答案挑出来了
        int n *= 2 , ans = 0;
        for(int k = 1; k * k < n; ++k){
            if(n % k != 0){
                continue;
            }
            if((n / k - (k - 1))%2 == 0){
                ans++;
            }
        }
        return ans;
    }
};

// 真的太秀了
文章来源:https://blog.csdn.net/ttxiaoxiaobai/article/details/135400409
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。