ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

yukicoder No.25 : 有限小数

概要

自然数N,Mが与えられ、NをMで割った商について考える。

この商が有限小数で表すことができるならば0以外の最後に現れる数を、表すことができないならば-1を出力せよ。

例えば、n=10,m=3ならば-1を、n=100,m=5ならば2を、n=7,m=5ならば4を出力する。

N,M≦2^63-1

http://yukicoder.me/problems/70

続きを読む

yukicoder No.23 : 技の選択

概要

体力Hの敵にダメージを与えて倒すことを考える。

こちらには2種類の攻撃方法がある。

  • 通常攻撃: 1回の攻撃でAダメージ与える。必中技。
  • 必殺技: 1回の攻撃でDダメージ与える。2/3の確率で命中。1/3の確率で攻撃を外す。

この2種類の攻撃を使って敵を倒すとき、攻撃回数の期待値の最小値を求めよ。

1≦H,A,D≦10000

http://yukicoder.me/problems/33

続きを読む

ABC #020 D : LCM Rush

概要

2つの正整数a,bの最小公倍数をLCM(a,b)とする。

2つの正整数N,Kが与えられるので、{ \displaystyle \sum_{i=1}^{N} LCM(i,K)}を10^9+7で割った余りを求めよ。

  • 100点解法:1≦N≦10^9, 1≦K≦100
  • 101点解法:1≦N,K≦10^9

http://abc020.contest.atcoder.jp/tasks/abc020_d

続きを読む