ぱーぽーの競プロ記

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

数学

yukicoder No.53 : 悪の漸化式

概要以下の漸化式が与えられるので、第N項ANを求めよ。 A0 = 4 A1 = 3 4Ak = 19Ak-1 - 12Ak-2 (k > 1) N≦100http://yukicoder.me/problems/80

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^6…

ABC #020 D : LCM Rush

概要2つの正整数a,bの最小公倍数をLCM(a,b)とする。2つの正整数N,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

yukicoder No.167 : N^M mod 10

概要N^M mod 10を求めよ。N,Mは非常に大きな値http://yukicoder.me/problems/373

ARC #034 C : 約数かつ倍数

概要正整数A、Bが与えられる。A!の約数かつB!の倍数であるような正整数の個数を1,000,000,007で割った余りを求めよ。1<=B<=A<=10^9 A-B<=100http://arc034.contest.atcoder.jp/tasks/arc034_3

Valentine's Day Round (BestCoder #030) B : Misaki's Kiss again

概要自然数Nが与えられる。gcd(N, M) == (N xor M)を満たす自然数Mを全て列挙せよ。0&ltN<=10^10 1<=M<=Nhttp://bestcoder.hdu.edu.cn/contests/contest_showproblem.php?pid=1002&cid=568

TopCoder SRM 628 Div1 Easy : DivisorsPower

解法・感想など 本番で解けなかったやつ。問題文読んだ瞬間、二分探索っぽい!って思ったが、1から順番にn^d(n)を列挙してみると n = 1: 1 n = 2: 4 n = 3: 9 n = 4: 64 n = 5: 25 n = 6: 1296 n = 7: 49 n = 8: 4096 n = 9: 729 n = 10: 10000 n = 11: 121 …