Statistics

Problem Statement for "CountingToOne"

Problem Statement

Consider a sequence f which satisfies,

  • f(1) = 1.
  • &Sigmad|n f(d) * f(n / d) = 1 for n > 1.
Your task is to calculate f(N). If your answer is of the from p / q, return (p * q-1) mod (109 + 7).

Definition

Class:
CountingToOne
Method:
calculate
Parameters:
long
Returns:
int
Method signature:
int calculate(long n)
(be sure your method is public)

Constraints

  • The value of N ranges from 1 to 1014 inclusive.

Examples

  1. 1

    Returns: 1

    f(1) = 1 by definition.

  2. 2

    Returns: 500000004

    For n = 2, f(1) * f(2)+f(2) * f(1) = 1. So f(2) = 1 / 2. (1 * 2-1) = 500000004 mod 109 + 7.

  3. 4

    Returns: 375000003

    For n = 4, f(1) * f(4) + f(2) * f(2) + f(4) * f(1) = 1. Also we know the values of f(1) = 1 and f(2) = 1/2. So f(4) = 3 / 8. (3 * 8-1) = 375000003 mod 109 + 7.

  4. 1000000000000

    Returns: 224797743

  5. 1401653119

    Returns: 500000004

  6. 341860583893

    Returns: 500000004

  7. 54442422241

    Returns: 375000003

  8. 999536628599

    Returns: 500000004

  9. 998889968795

    Returns: 250000002

  10. 999538264185

    Returns: 562500004

  11. 999411956885

    Returns: 125000001

  12. 999857040823

    Returns: 250000002

  13. 562987333

    Returns: 250000002

  14. 997863694481

    Returns: 125000001

  15. 998767396481

    Returns: 250000002

  16. 1684951201

    Returns: 500000004

  17. 1321196369

    Returns: 125000001

  18. 982450929

    Returns: 250000002

  19. 1355038273

    Returns: 250000002

  20. 999667259274

    Returns: 562500004

  21. 1892241411

    Returns: 562500004

  22. 1872020353

    Returns: 421875003

  23. 999372830273

    Returns: 562500004

  24. 998840896457

    Returns: 125000001

  25. 999919052957

    Returns: 125000001

  26. 999172533589

    Returns: 125000001

  27. 999970140849

    Returns: 562500004

  28. 1461529391

    Returns: 562500004

  29. 998862398399

    Returns: 500000004

  30. 998369247875

    Returns: 703125005

  31. 998632142082

    Returns: 421875003

  32. 1545160705

    Returns: 562500004

  33. 999739053153

    Returns: 703125005

  34. 459932209

    Returns: 125000001

  35. 999509896372

    Returns: 843750006

  36. 999129112971

    Returns: 281250002

  37. 999192399363

    Returns: 421875003

  38. 999721327333

    Returns: 125000001

  39. 999662909441

    Returns: 281250002

  40. 135337941

    Returns: 687500005

  41. 999199853839

    Returns: 562500004

  42. 182195157

    Returns: 250000002

  43. 767343507

    Returns: 125000001

  44. 999863230729

    Returns: 125000001

  45. 999998736213

    Returns: 125000001

  46. 998492710015

    Returns: 562500004

  47. 65214507758400

    Returns: 628571321

  48. 55898149507200

    Returns: 97618927

  49. 93163582512000

    Returns: 759637078

  50. 97821761637600

    Returns: 463636260

  51. 97821761637600

    Returns: 463636260

  52. 93163582512000

    Returns: 759637078

  53. 65214507758400

    Returns: 628571321

  54. 48910880818800

    Returns: 515151400

  55. 55898149507200

    Returns: 97618927

  56. 46581791256000

    Returns: 587301467

  57. 32607253879200

    Returns: 958441443

  58. 27949074753600

    Returns: 566666540

  59. 26985313555200

    Returns: 981026622

  60. 18632716502400

    Returns: 111564488

  61. 13492656777600

    Returns: 646428394

  62. 777600000

    Returns: 242023538

  63. 100000000000000

    Returns: 801213761

  64. 100000004107

    Returns: 500000004

  65. 100

    Returns: 265625002

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: