[原创]LIGHT OJ 1278 Sum of Consecutive Integers [因子个数]【数论】

Tabris

CSDN模板数论

发布于：2016年10月25日

次浏览

[原创]LIGHT OJ 1278 Sum of Consecutive Integers [因子个数]【数论】

2016-10-25 19:37:29 Tabris_ 阅读数：758

博客爬取于 2020-06-14 22:42:59
以下为正文

版权声明：本文为 Tabris 原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/52926338

题目链接：http://vjudge.net/contest/137260#problem/W
-----------------------------------.
Sum of Consecutive Integers
Time Limit:2000MS Memory Limit:32768KB 64bit IO Format:%lld & %llu

Description
Given an integer N, you have to find the number of ways you can express N as sum of consecutive integers. You have to use at least two integers.

For example, N = 15 has three solutions, (1+2+3+4+5), (4+5+6), (7+8).

Input
Input starts with an integer T (≤ 200), denoting the number of test cases.

Each case starts with a line containing an integer N (1 ≤ N ≤ 1014).

Output
For each case, print the case number and the number of ways to express N as sum of consecutive integers.

Sample Input
5
10
15
12
36
828495
Sample Output
Case 1: 1
Case 2: 3
Case 3: 1
Case 4: 2
Case 5: 47

-------------------------------------.

题目大意 :
给你一个数 N ，然后问你 一些连续的数和 等于 N 的种类数

解题思路：
首先
N=a+（a+1）+（a+2）+（a+3）+...+（a+k-1）
=（a+a+k-1）k/2 =（2a+k-1）*k/2

然后把式子转换一下
得到这样的结果
2N/K-K=2a-1

我们能够知道 2a-1 是奇数 所以 2N/K 与 K 之间一定是一个奇数一个偶数的
那么这时候只要求有多少种 K 的值能够满足 这个式子 就可以了
1）K 为奇数 2N/K 为偶数
2）K 为偶数 2 N/K 为奇数
这时候 2N/K 和/K 都是 2N 的奇因子 其中上述两种情况在计算中不会出现重叠的时候 所以计算两者加和就行了也就是 N*2 的奇因子，

综上所述 ：N 的奇数因子的个数即为解。

然后只要求 N 得奇质因子的个数就行了
根据算数基本定理讲 N 展开
N=p1^a1p2^a2p2^a2*...*pn^an

然后根据因子个数的公式 ∏ i_n （ai+1）
由于我们求的是奇质因子的个数 所有质因子为偶数的时候就不用计算了 当然质因子中只有 2 一个是偶数

附本题代码
------------------------.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

//#include <bits/stdc++.h>
# include <stdio.h>
# include <iostream>
# include <algorithm>
# include <string.h>
# include <cmath>
using namespace std;

# define INF 0x3f3f3f3f
# define pb push_back
# define abs(a) (a)>0?(a):-(a)
# define min(a,b) (a)>(b)?(a):(b)
# define lalal puts("*******")
typedef long long int LL ;
typedef unsigned long long int LLu ;
/*******************************/

const int MOD = 10086;
const int N = 1e7+5;

int prime[700000],kp;
bool Is_or[N];

void shacker()
{
    for(int i=0;i<N;i++) Is_or[i]=1;
    for(int i=2;i<N;i++)
    {
        if(Is_or[i]) prime[kp++]=i;
        for(int j=0;j<kp&&i*prime[j]<N;j++)
        {
            Is_or[i*prime[j]]=0;
            if(0==i%prime[j]) break;
        }
    }
    //printf("%d\n",kp);
    return ;
}

LL solve(LL a)
{
    LL num;
    LL result=1;
    while(a%2==0) a/=2;
    for(int i=1;i<kp&&a>=prime[i];i++)
    {
        num=0;
        while(a%prime[i]==0) a/=prime[i],num++;
        //printf("%I64d-%I64d(%d)  ",a,num,prime[i]);
        result*=(num+1);
    }
    //puts("");
    if(a>1) result*=2;
    return result-1;
}

int main()
{
    shacker();
    int _;
    while(~scanf("%d",&_))
    {
        int kase = 0;
        while(_--)
        {
            LL n;
            scanf("%lld",&n);
            printf("Case %d: %lld\n",++kase,solve(n));
        }
    }
    return 0;
}

本页文档最后更新于：2021年5月16日

CSDN