提出 #3887594 - AtCoder Beginner Contest 020

コンテスト時間: 2015-03-21 21:00:00+0900 ~ 2015-03-21 23:00:00+0900 (120分) AtCoderホームへ戻る

提出 #3887594

ソースコード拡げる

#include <bits/stdc++.h>
#define N 1000000007
using namespace std;

// calculate |gcd|.
// if  ether num is 0, return 0
long long GCD(long long left, long long right) {
  if(left == 0 || right == 0) return 0;
  if(left < 0) left *= -1;
  if(right < 0) right *= -1;
  if(left < right) swap(left, right);
  long long nextnum, ansgcd = -1;
  while(ansgcd == -1) {
    nextnum = left % right;
    if(nextnum == 0) ansgcd = right;
    left = right;
    right = nextnum;
  }
  return ansgcd;
}
long long n, k;

long long solve();
long long calc(long long x);
long long calcs(long long p, long long x);
long long cnt(long long x);

int main() {
  cin >> n >> k;
  cout << solve() << endl;
  return 0;
}

long long solve() {
  long long ans = 0;
  for(long long i = 1; i * i <= k; ++i)
    if(k % i == 0) {
      ans += calc(i);
      ans %= N;
      if(k / i != i) ans += calc(k / i);
      ans %= N;
    }
  return ans;
}

// GCD(i,k) = x
long long calc(long long x) {
  return calcs(n / x, k / x) * x % N * (k / x) % N;
}

// 1~p, GCD(i,x) = 1
long long calcs(long long p, long long x) {
  long long ans = (p * (p + 1) / 2) % N;
  for(long long i = 1; i * i <= x; ++i)
    if(x % i == 0) {
      long long now = p / i, ch = cnt(i);
      now = (now * (now + 1) / 2) % N * i % N;
      if(ch == 0 || i == 1)
        now = 0;
      else if(ch % 2 == 1)
        now *= -1;
      ans += now;
      while(ans < 0) ans += N;
      ans %= N;
      if(x / i == i) continue;
      now = p / (x / i), ch = cnt(x / i);
      now = (now * (now + 1) / 2) % N * (x / i) % N;
      if(ch == 0)
        now = 0;
      else if(ch % 2 == 1)
        now *= -1;
      ans += now;
      while(ans < 0) ans += N;
      ans %= N;
    }
  return ans;
}

long long cnt(long long x) {
  long long ans = 0;
  for(long long i = 2; i * i <= x; ++i)
    if(x % i == 0) {
      if(x % (i * i) == 0) return 0;
      x /= i;
      ++ans;
    }
  if(x > 1) ++ans;
  return ans;
}

提出情報

提出日時	2018-12-28 23:41:00+0900
問題	D - LCM Rush
ユーザ	m_tsubasa
言語	C++14 (GCC 5.4.1)
得点	101
コード長	2028 Byte
結果	AC
実行時間	20 ms
メモリ	256 KiB

ジャッジ結果

セット名

Sample

Subtask1

Subtask2

Subtask3

Subtask4

得点 / 配点

0 / 0

5 / 5

10 / 10

85 / 85

1 / 1

結果

× 4

× 16

× 32

× 48

× 89

セット名	テストケース
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

ケース名	結果	実行時間	メモリ
subtask0_sample_01.txt	AC	1 ms	256 KiB
subtask0_sample_02.txt	AC	1 ms	256 KiB
subtask0_sample_03.txt	AC	1 ms	256 KiB
subtask0_sample_04.txt	AC	5 ms	256 KiB
subtask1_01.txt	AC	1 ms	256 KiB
subtask1_02.txt	AC	1 ms	256 KiB
subtask1_03.txt	AC	1 ms	256 KiB
subtask1_04.txt	AC	1 ms	256 KiB
subtask1_05.txt	AC	1 ms	256 KiB
subtask1_06.txt	AC	1 ms	256 KiB
subtask1_07.txt	AC	1 ms	256 KiB
subtask1_08.txt	AC	1 ms	256 KiB
subtask1_09.txt	AC	1 ms	256 KiB
subtask1_10.txt	AC	1 ms	256 KiB
subtask1_11.txt	AC	1 ms	256 KiB
subtask1_12.txt	AC	1 ms	256 KiB
subtask1_13.txt	AC	1 ms	256 KiB
subtask1_14.txt	AC	1 ms	256 KiB
subtask1_15.txt	AC	1 ms	256 KiB
subtask2_16.txt	AC	1 ms	256 KiB
subtask2_17.txt	AC	1 ms	256 KiB
subtask2_18.txt	AC	1 ms	256 KiB
subtask2_19.txt	AC	1 ms	256 KiB
subtask2_20.txt	AC	1 ms	256 KiB
subtask2_21.txt	AC	1 ms	256 KiB
subtask2_22.txt	AC	1 ms	256 KiB
subtask2_23.txt	AC	1 ms	256 KiB
subtask2_24.txt	AC	1 ms	256 KiB
subtask2_25.txt	AC	1 ms	256 KiB
subtask2_26.txt	AC	1 ms	256 KiB
subtask2_27.txt	AC	1 ms	256 KiB
subtask2_28.txt	AC	1 ms	256 KiB
subtask2_29.txt	AC	1 ms	256 KiB
subtask2_30.txt	AC	1 ms	256 KiB
subtask3_31.txt	AC	1 ms	256 KiB
subtask3_32.txt	AC	1 ms	256 KiB
subtask3_33.txt	AC	1 ms	256 KiB
subtask3_34.txt	AC	1 ms	256 KiB
subtask3_35.txt	AC	1 ms	256 KiB
subtask3_36.txt	AC	1 ms	256 KiB
subtask3_37.txt	AC	1 ms	256 KiB
subtask3_38.txt	AC	1 ms	256 KiB
subtask3_39.txt	AC	1 ms	256 KiB
subtask3_40.txt	AC	1 ms	256 KiB
subtask3_41.txt	AC	1 ms	256 KiB
subtask3_42.txt	AC	1 ms	256 KiB
subtask3_43.txt	AC	1 ms	256 KiB
subtask3_44.txt	AC	1 ms	256 KiB
subtask3_45.txt	AC	1 ms	256 KiB
subtask4_46.txt	AC	4 ms	256 KiB
subtask4_47.txt	AC	4 ms	256 KiB
subtask4_48.txt	AC	20 ms	256 KiB
subtask4_49.txt	AC	19 ms	256 KiB
subtask4_50.txt	AC	19 ms	256 KiB
subtask4_51.txt	AC	20 ms	256 KiB
subtask4_52.txt	AC	19 ms	256 KiB
subtask4_53.txt	AC	19 ms	256 KiB
subtask4_54.txt	AC	18 ms	256 KiB
subtask4_55.txt	AC	18 ms	256 KiB
subtask4_56.txt	AC	18 ms	256 KiB
subtask4_57.txt	AC	18 ms	256 KiB
subtask4_58.txt	AC	18 ms	256 KiB
subtask4_59.txt	AC	18 ms	256 KiB
subtask4_60.txt	AC	2 ms	256 KiB
subtask4_61.txt	AC	2 ms	256 KiB
subtask4_62.txt	AC	2 ms	256 KiB
subtask4_63.txt	AC	4 ms	256 KiB
subtask4_64.txt	AC	17 ms	256 KiB
subtask4_65.txt	AC	20 ms	256 KiB
subtask4_66.txt	AC	20 ms	256 KiB
subtask4_67.txt	AC	18 ms	256 KiB
subtask4_68.txt	AC	13 ms	256 KiB
subtask4_69.txt	AC	13 ms	256 KiB
subtask4_70.txt	AC	1 ms	256 KiB
subtask4_71.txt	AC	1 ms	256 KiB
subtask4_72.txt	AC	2 ms	256 KiB
subtask4_73.txt	AC	2 ms	256 KiB
subtask4_74.txt	AC	4 ms	256 KiB
subtask4_75.txt	AC	2 ms	256 KiB
subtask4_76.txt	AC	3 ms	256 KiB
subtask4_77.txt	AC	3 ms	256 KiB
subtask4_78.txt	AC	1 ms	256 KiB
subtask4_79.txt	AC	1 ms	256 KiB
subtask4_80.txt	AC	1 ms	256 KiB
subtask4_81.txt	AC	1 ms	256 KiB
subtask4_82.txt	AC	2 ms	256 KiB
subtask4_83.txt	AC	2 ms	256 KiB
subtask4_84.txt	AC	3 ms	256 KiB
subtask4_85.txt	AC	2 ms	256 KiB