Sum of Consecutive Integers LightOJ - 1278————（算术基本定理+容斥）

r囧r小猫 2022-05-18 02:58 164阅读 0赞

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

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

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

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

**Output**  
For each case, print the case number and the number of ways to expressN  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  N <script type="math/tex" id="MathJax-Element-6317">N</script>的方法有多少种？

也就是找奇数因子的个数

--------------------

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<cmath>
    #include<algorithm>
    using  namespace std;
    typedef long long LL;
    const int maxn = 10000000, INF = 0x7fffffff;
    int primes[1000000];
    bool vis[maxn];
    int ans = 0;
    void init()
    {
        memset(vis,0,sizeof(vis));
        for(int i=2; i<maxn; i++)
        {
            if(vis[i]) continue;
            primes[ans++] = i;
            for(LL j=(LL)i*i; j<maxn; j+=i)
                vis[j] = 1;
        }
    }
    int main()
    {
        init();
        int t;
        scanf("%d",&t);
        int kase=0;
        while(t--)
        {
             LL n, res = 1;
            cin>> n;
            for(int i=0; i<ans && primes[i]*primes[i] <= n; i++)
            {
                LL cnt2 = 0;
                while(n % primes[i] == 0)
                {
                    n /= primes[i];
                    cnt2++;
                }
                if(cnt2 > 0 && primes[i] % 2)
                    res *= (cnt2 + 1);
            }
            if(n > 1 && n % 2)
            {
                res *= 2;
            }
            printf("Case %d: %lld\n", ++kase, res - 1);
        }
        return 0;
    }