Factors

View as PDF
Submit solution
Points: 7
Time limit: 1.0s
Memory limit: 256M
Author:
andrewtam
Problem type

You are given two positive integers, A and B. How many factors does the sum of the integers from A to B inclusive have?

Input Specification

The input contains one line with two space-separated integers, A and B.

Output Specification

Output a single integer, the number of factors of the sum of the integers from A to B inclusive.

Constraints

1 \le A \le B \le 10^{12}

Sample Input

1 3

Sample Output

4

Comments


  • 0
    stanwww  commented on Oct. 20, 2024, 3:36 p.m. ← edited

    Hint: there is integer overflow using 64 bits when you add all integers together. Plus factoring the sum of all integers summed up is too slow O(square root of the sum) which can be as high as 10^25. Try to find another way to do this.


  • -1
    icerv1  commented on Dec. 7, 2022, 7:51 p.m.

    Can anyone help me with test case 4? 48 is marked as incorrect, but I don't understand why.

    The input is 1 1000000000000. The sum of the numbers in between should be 1001882602603448320. I have calculated its factors to be the following.

    1, 1001882602603448320

    2, 500941301301724160

    4, 250470650650862080

    5, 200376520520689664

    8, 125235325325431040

    10, 100188260260344832

    16, 62617662662715520

    20, 50094130130172416

    32, 31308831331357760

    40, 25047065065086208

    64, 15654415665678880

    80, 12523532532543104

    128, 7827207832839440

    160, 6261766266271552

    256, 3913603916419720

    320, 3130883133135776

    512, 1956801958209860

    640, 1565441566567888

    1024, 978400979104930

    1280, 782720783283944

    2048, 489200489552465

    2560, 391360391641972

    5120, 195680195820986

    10240, 97840097910493

    This makes for 24 pairs, or 48 total individual factors. Alternatively, the number of factors can be calculated through prime numbers. I have calculated the prime factorisation of to be (2^11)(5^1)(97840097910493^1). Taking the exponents of each, you can deduce that the number of factors should be (11 + 1)(1 + 1)(1 + 1), which is equal to 48.

    What am I overlooking?


    • 1
      chika  commented on Dec. 7, 2022, 9:34 p.m.

      What is the sum of the first 10^{12} positive integers? Please show your work.


      • 1
        icerv1  commented on Dec. 7, 2022, 11:41 p.m. ← edited

        I was using the formula y = x(x + 1)/2 on a separate program I made, but having redone the calculation separately, my program didn't get it right. Thanks.


        • 1
          gary4988  commented on March 31, 2023, 1:13 a.m. ← edited

          I am at the same place where you were before. But how did you get out?

          In test case 4, A = 1, B = 10^{12}, I got sum(A,B) = 1001882602603448320. and the answer is 48.

          Thanks.