ABC142総括

C

argsortすればいいだけ。O(NlogN)

D

正整数 $A,B$ が与えられます。

$A$ と $B$ の正の公約数の中からいくつかを選びます。

ただし、選んだ整数の中のどの異なる $2$ つの整数についても互いに素でなければなりません。

最大でいくつ選べるでしょうか。

gcd(A,B)をユークリッドの互除法で求めた後、素因数分解して素因数の数+1が答え。

求め方が下手くそでTLEしたので記録しておく。

[tex:

A,B <= 10^12なので\sqrt(N)程度のアルゴリズムが必要

]

元となる考え方はNに対してsqrt(N)以上の素因数はせいぜい1個しかないということ

int main() {

  ll A, B;

  cin >> A >> B;

  ll C = gcd(A, B);

  ll res = 1;

  ll N = C; //もとの数をNに記録

  ll i = 2;

  while (i * i <= N) { //素因数は少なくとも1個を除いてsqrt(N)まで

      if (C % i == 0) res++; //割れるなら素因数なのでカウント

      while (C % i == 0) C = C / i;//その素因数が含まれなくなるまで割る

      i++;

  }

  if (C > 1) res++; //素因数が残った場合

  cout << res << "\n";

}

 

E

鍵のかかった宝箱が $N$ 個あり、$1$ から $N$ までの番号がつけられています。

店で $M$ 個の鍵が売られています。$i$ 個目の鍵は $a_i$ 円で販売されており、$b_i$ 種類の宝箱 $c_{i1}$ , $c_{i2}$ , ..., $c_{i{b}_i}$ を開けることが出来ます。購入した鍵は何度でも使うことが出来ます。

全ての宝箱を開ける為に必要な費用の最小値を答えてください。全ての宝箱を開けることが不可能である場合は $-1$ を出力してください。

当初最小費用流を使おうとしたが考えたらE問題でそのレベルは出ない。

DPで解ける。