首页 > 代码库 > LightOj 1278 - Sum of Consecutive Integers（求奇因子的个数）
LightOj 1278 - Sum of Consecutive Integers（求奇因子的个数）
题目链接：http://lightoj.com/volume_showproblem.php?problem=1278
题意：给你一个数n(n<=10^14)，然后问n能用几个连续的数表示;
例如: 15 = 7+8 = 4+5+6 = 1+2+3+4+5，所以15对应的答案是3，有三种;
我们现在相当于已知等差数列的和sum = n, 另首项为a1,共有m项，那么am = a1+m-1；
sum = m*(a1+a1+m-1)/2 -----> a1 = sum/m - (m-1)/2
a1 和 m 一定是整数，所以sum%m = 0 并且(m-1)%2=0, 所以m是sum的因子，并且要是奇数；
所以我们只要求n的奇数因子的个数即可，求一个数的因子个数是所有素数因子的幂+1,相乘起来就是，那么素数只有2是偶数，
所以奇数因子的个数就是所有 素数因子（除2之外）+1的乘积，当然要m一定要大于1，所以要减去1，除去因子1的情况；
#include <stdio.h>#include <iostream>#include <algorithm>#include <string.h>using namespace std;typedef long long LL;const double eps = 1e-10;const int N = 1e7+1;int p[N/10], k;bool f[N];void Init(){ for(int i=2; i<N; i++) { if(!f[i]) p[k++] = i; for(int j=i+i; j<N; j+=i) f[j] = true; }}int main(){ Init(); int T, t = 1; scanf("%d", &T); while(T --) { LL n, ans = 1; scanf("%lld", &n); int flag = 0; for(int i=0; i<k && (LL)p[i]*p[i]<=n; i++) { LL cnt = 0; while(n%p[i] == 0) { cnt ++; n /= p[i]; } if(i)///不能算 2 ； ans *= cnt+1; } if(n > 2) ans *= 2; ans -= 1;///减去1的情况； printf("Case %d: %lld\n", t++, ans); } return 0;}
LightOj 1278 - Sum of Consecutive Integers（求奇因子的个数）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。