BBAD - Breaking Math


Walter is a high school chemistry teacher. After being diagnosed with stage 3A, inoperable lung cancer, Walter is devastated. Realizing he does not have much time left, a desperate Walter resorts to cooking crystal methamphetamine, in order to provide for his treatment and family. And guess what, he mixes up with some really horrible people in the process.

The worst of them is Heisenburg, a badass physicist and the ultimate drug lord. Walter needs Heisenburg’s active support to distribute the methamphetamine he produces. Alas, Heisenburg is a cautious man. Heisenburg is initially skeptical about Walter, and decides to give the following problem to Walter in order to prove his worth.

w(n) is defined to be the number of distinct prime factors of n, for example:

w(1) = 0, w(2) = 1, w(3) = 1, w(4) = 1, w(5) = 1, w(6) = 2, w(30) = 3

f(n, k) = ∑ kw(i) where 1 ≤ i ≤ n

For instance, f(6,2) = 2w(1) + 2w(2) + 2w(3) + 2w(4) + 2w(5) + 2w(6) = 13

Given n and k, calculate f(n, k).

Input

The first line contains an integer t, denoting the number of test cases. Each of the next t lines contains two integers, n and k, separated by a single space. Sum of n will not exceed 1011 in an input file.

Constraints

  • 1 ≤ t ≤ 100
  • 1 ≤ n ≤ 1011
  • 1 ≤ k ≤ 10
  • 1 ≤ ∑n ≤ 1011
  • Output

    For each case, output a line of the format Case X: Y, where X is the case number, starting from 1, and Y is the required answer. You can safely assume that the answer will fit in a signed 64 bit integer.

    Sample Input

    10
    1 1
    2 2
    3 3
    4 4
    5 5
    6 6
    7 7
    8 8
    9 9
    10 10
    

    Sample Output

    Case 1: 1
    Case 2: 3
    Case 3: 7
    Case 4: 13
    Case 5: 21
    Case 6: 61
    Case 7: 85
    Case 8: 113
    Case 9: 145
    Case 10: 271
    



    hide comments
    Ishan: 2022-10-27 13:16:26

    I have found a way to do in to do till10^9 . :( . my recurrence relation has 3 params probably it can be done with 2 params.

    [Lakshman]: 2020-06-21 15:42:58

    @sgtlaugh Can you give some hint?

    -> Sure thing @Lakshman. My actual solution is similar to that of https://www.spoj.com/problems/APS2/. Another hint, think how you can use inclusion-exclusion or methods like fast prime counting to calculate it faster.

    =(Lakshman)=> Thanks. @sgtlaugh

    Last edit: 2020-06-23 17:59:06
    Francky: 2020-06-11 11:17:56

    Please update description :
    -<strong>f(n, k) = ∑ kw(i)</strong>
    +<strong>f(n, k) = ∑ k<sup>w(i)</sup></strong> for <strong>1 ≤ i ≤ n</strong>

    -> Thanks for noticing, updated!

    Last edit: 2020-06-11 23:23:38
    nadstratosfer: 2020-06-11 01:06:55

    I don't know the solution to this one, but an easy version with n < 10^7, k < 140 and t > 10000 would be fun to solve efficiently as well -- please consider setting it. Perhaps in Tutorial, but IMHO it'd make a popular classical problem too.

    -> I like this suggestion, will do. That'd be a good mid level classical problem.

    Last edit: 2020-06-11 23:25:27

    Added by:sgtlaugh
    Date:2020-06-10
    Time limit:5s
    Source limit:50000B
    Memory limit:1536MB
    Cluster: Cube (Intel G860)
    Languages:All
    Resource:Own Problem