Submission #365793

Source Code Expand

def gcd(x, y)
  loop do
    m = x % y
    return y if m == 0
    x, y = y, m
  end
end
N, K = gets.split.map(&:to_i)
M = 1000000007
Q, R = N.divmod(K)
p (1..K).inject(0) {|s, k|
  a = k / gcd(k, K)
  b = (k + K) / gcd(k + K, K)
  n = k <= R ? Q + 1 : Q
  (s + (2 * a - b) * n + (n + 1) * n / 2 * (b - a)) % M
} * K % M

Submission Info

Submission Time
Task D - LCM Rush
User snipsnipsnip
Language Ruby (2.1.5p273)
Score 100
Code Size 333 Byte
Status TLE
Exec Time 2040 ms
Memory 5076 KiB

Judge Result

Set Name Sample Subtask1 Subtask2 Subtask3 Subtask4
Score / Max Score 0 / 0 5 / 5 10 / 10 85 / 85 0 / 1
Status
AC × 3
TLE × 1
AC × 16
AC × 32
AC × 48
AC × 50
TLE × 39
Set Name Test Cases
Sample subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask0_sample_04.txt
Subtask1 subtask0_sample_01.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt
Subtask2 subtask0_sample_01.txt, subtask0_sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask2_16.txt, subtask2_17.txt, subtask2_18.txt, subtask2_19.txt, subtask2_20.txt, subtask2_21.txt, subtask2_22.txt, subtask2_23.txt, subtask2_24.txt, subtask2_25.txt, subtask2_26.txt, subtask2_27.txt, subtask2_28.txt, subtask2_29.txt, subtask2_30.txt
Subtask3 subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask2_16.txt, subtask2_17.txt, subtask2_18.txt, subtask2_19.txt, subtask2_20.txt, subtask2_21.txt, subtask2_22.txt, subtask2_23.txt, subtask2_24.txt, subtask2_25.txt, subtask2_26.txt, subtask2_27.txt, subtask2_28.txt, subtask2_29.txt, subtask2_30.txt, subtask3_31.txt, subtask3_32.txt, subtask3_33.txt, subtask3_34.txt, subtask3_35.txt, subtask3_36.txt, subtask3_37.txt, subtask3_38.txt, subtask3_39.txt, subtask3_40.txt, subtask3_41.txt, subtask3_42.txt, subtask3_43.txt, subtask3_44.txt, subtask3_45.txt
Subtask4 subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask0_sample_04.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask2_16.txt, subtask2_17.txt, subtask2_18.txt, subtask2_19.txt, subtask2_20.txt, subtask2_21.txt, subtask2_22.txt, subtask2_23.txt, subtask2_24.txt, subtask2_25.txt, subtask2_26.txt, subtask2_27.txt, subtask2_28.txt, subtask2_29.txt, subtask2_30.txt, subtask3_31.txt, subtask3_32.txt, subtask3_33.txt, subtask3_34.txt, subtask3_35.txt, subtask3_36.txt, subtask3_37.txt, subtask3_38.txt, subtask3_39.txt, subtask3_40.txt, subtask3_41.txt, subtask3_42.txt, subtask3_43.txt, subtask3_44.txt, subtask3_45.txt, subtask4_46.txt, subtask4_47.txt, subtask4_48.txt, subtask4_49.txt, subtask4_50.txt, subtask4_51.txt, subtask4_52.txt, subtask4_53.txt, subtask4_54.txt, subtask4_55.txt, subtask4_56.txt, subtask4_57.txt, subtask4_58.txt, subtask4_59.txt, subtask4_60.txt, subtask4_61.txt, subtask4_62.txt, subtask4_63.txt, subtask4_64.txt, subtask4_65.txt, subtask4_66.txt, subtask4_67.txt, subtask4_68.txt, subtask4_69.txt, subtask4_70.txt, subtask4_71.txt, subtask4_72.txt, subtask4_73.txt, subtask4_74.txt, subtask4_75.txt, subtask4_76.txt, subtask4_77.txt, subtask4_78.txt, subtask4_79.txt, subtask4_80.txt, subtask4_81.txt, subtask4_82.txt, subtask4_83.txt, subtask4_84.txt, subtask4_85.txt
Case Name Status Exec Time Memory
subtask0_sample_01.txt AC 52 ms 4992 KiB
subtask0_sample_02.txt AC 51 ms 4844 KiB
subtask0_sample_03.txt AC 50 ms 4844 KiB
subtask0_sample_04.txt TLE 2034 ms 4972 KiB
subtask1_01.txt AC 51 ms 4844 KiB
subtask1_02.txt AC 50 ms 4844 KiB
subtask1_03.txt AC 50 ms 4844 KiB
subtask1_04.txt AC 50 ms 4840 KiB
subtask1_05.txt AC 54 ms 4840 KiB
subtask1_06.txt AC 51 ms 4840 KiB
subtask1_07.txt AC 52 ms 4840 KiB
subtask1_08.txt AC 53 ms 4980 KiB
subtask1_09.txt AC 53 ms 4840 KiB
subtask1_10.txt AC 54 ms 4984 KiB
subtask1_11.txt AC 53 ms 4844 KiB
subtask1_12.txt AC 52 ms 4844 KiB
subtask1_13.txt AC 53 ms 4840 KiB
subtask1_14.txt AC 53 ms 4840 KiB
subtask1_15.txt AC 51 ms 4840 KiB
subtask2_16.txt AC 50 ms 4844 KiB
subtask2_17.txt AC 53 ms 4940 KiB
subtask2_18.txt AC 52 ms 4840 KiB
subtask2_19.txt AC 55 ms 4828 KiB
subtask2_20.txt AC 52 ms 4844 KiB
subtask2_21.txt AC 51 ms 4844 KiB
subtask2_22.txt AC 52 ms 4844 KiB
subtask2_23.txt AC 54 ms 4840 KiB
subtask2_24.txt AC 54 ms 4880 KiB
subtask2_25.txt AC 54 ms 4844 KiB
subtask2_26.txt AC 54 ms 4888 KiB
subtask2_27.txt AC 52 ms 4840 KiB
subtask2_28.txt AC 54 ms 4844 KiB
subtask2_29.txt AC 51 ms 4840 KiB
subtask2_30.txt AC 50 ms 4844 KiB
subtask3_31.txt AC 50 ms 4844 KiB
subtask3_32.txt AC 53 ms 4840 KiB
subtask3_33.txt AC 50 ms 4844 KiB
subtask3_34.txt AC 50 ms 4844 KiB
subtask3_35.txt AC 52 ms 4844 KiB
subtask3_36.txt AC 51 ms 4844 KiB
subtask3_37.txt AC 50 ms 4932 KiB
subtask3_38.txt AC 51 ms 4844 KiB
subtask3_39.txt AC 52 ms 4844 KiB
subtask3_40.txt AC 52 ms 4844 KiB
subtask3_41.txt AC 50 ms 4840 KiB
subtask3_42.txt AC 52 ms 4844 KiB
subtask3_43.txt AC 50 ms 4844 KiB
subtask3_44.txt AC 52 ms 4844 KiB
subtask3_45.txt AC 52 ms 4836 KiB
subtask4_46.txt TLE 2034 ms 4972 KiB
subtask4_47.txt TLE 2033 ms 4972 KiB
subtask4_48.txt TLE 2033 ms 4968 KiB
subtask4_49.txt TLE 2034 ms 4972 KiB
subtask4_50.txt TLE 2034 ms 4972 KiB
subtask4_51.txt TLE 2033 ms 4972 KiB
subtask4_52.txt TLE 2034 ms 4976 KiB
subtask4_53.txt TLE 2034 ms 4948 KiB
subtask4_54.txt TLE 2034 ms 4972 KiB
subtask4_55.txt TLE 2034 ms 4968 KiB
subtask4_56.txt TLE 2034 ms 4968 KiB
subtask4_57.txt TLE 2034 ms 4972 KiB
subtask4_58.txt TLE 2040 ms 4968 KiB
subtask4_59.txt TLE 2033 ms 4964 KiB
subtask4_60.txt TLE 2033 ms 5076 KiB
subtask4_61.txt TLE 2032 ms 4968 KiB
subtask4_62.txt TLE 2037 ms 5024 KiB
subtask4_63.txt TLE 2034 ms 5072 KiB
subtask4_64.txt TLE 2034 ms 4972 KiB
subtask4_65.txt TLE 2035 ms 5024 KiB
subtask4_66.txt TLE 2034 ms 4972 KiB
subtask4_67.txt TLE 2034 ms 4972 KiB
subtask4_68.txt TLE 2035 ms 4988 KiB
subtask4_69.txt TLE 2034 ms 4972 KiB
subtask4_70.txt TLE 2034 ms 4972 KiB
subtask4_71.txt AC 54 ms 4840 KiB
subtask4_72.txt TLE 2033 ms 4968 KiB
subtask4_73.txt TLE 2033 ms 5012 KiB
subtask4_74.txt TLE 2033 ms 4968 KiB
subtask4_75.txt TLE 2033 ms 4972 KiB
subtask4_76.txt TLE 2033 ms 4956 KiB
subtask4_77.txt TLE 2032 ms 4972 KiB
subtask4_78.txt TLE 2033 ms 4948 KiB
subtask4_79.txt TLE 2033 ms 4972 KiB
subtask4_80.txt AC 1930 ms 4844 KiB
subtask4_81.txt TLE 2033 ms 4956 KiB
subtask4_82.txt TLE 2033 ms 4968 KiB
subtask4_83.txt TLE 2034 ms 4948 KiB
subtask4_84.txt TLE 2033 ms 4948 KiB
subtask4_85.txt TLE 2033 ms 4960 KiB