roiti46's blog

主に競プロ問題の解説を載せてます

Atcoder Regular Contest 034 A:主席、 B:方程式、 C:約数かつ倍数

ABCDの4問セット。CまではいつものARCよりも簡単。問題はこちら

A: 主席

学生N人の5つの科目のテストの得点をそれぞれ与えられる。5つめのテストの点数だけ110/900倍するとして、もっとも得点の多い学生の得点を答える。

解法

問題文通りにやるだけ。

N = int(raw_input())
ans = 0
for loop in xrange(N):
    a,b,c,d,e = map(int,raw_input().split())
    ans = max(ans, a+b+c+d+e*110./900.)
print "%.6f"%ans

B: 方程式

f(123) = 1+2+3 のようにある数字の各桁を足し合わせた値を返す関数がある。正の整数N (≦ 1018)が与えられるので、正の整数xのうち x+f(x) = N となるようなxの個数とその値を答える。

解法

Nが大きいのですべての数について試すことはできない。しかし、Nは最大18桁で f(N) ≦ 9*18 = 162 であるので、N-200からNまでのxについて x+f(x) に代入してNになるかどうか確かめればいい。

def f(n):
    return sum(int(s) for s in str(n))
    
N = int(raw_input())
ans = []
for n in xrange(max(0,N-200),N+1):
    if n+f(n) == N:
        ans.append(n)
print len(ans)
for a in ans: print a

C: 約数と倍数

AとBが与えられる (1 ≦ B ≦ A ≦ 109, A-B ≦ 100)。A!の約数かつB!の倍数となる正の整数はいくつかあるかを100,000,007で割った余りで答える。

解法

A!の約数かつB!の倍数となれるのは、B!にA(A-1)...(B+1)が有している素因数を、(有している個数を超えない数で)任意の個数かけたものである。A!はB!にA(A-1)...(B+1)をかけたものであるので、上記の素因数の積によってできる数はA(A-1)...(B+1)の約数である。したがって、この素因数の積によってできた数にB!をかけると、問題文の条件を満たす数となる。つまり、やるべきはB+1からAまでの素因数の数をカウントすることである。

高校数学でも出てきたが、素因数p1,p2,p3...がそれぞれa1,a2,a3...個あったときに、これらの素因数の積から作ることのできる数は合計で、(1+a1)(1+a2)...個である。

from collections import defaultdict
mod = 10**9+7
 
def calc(n):
    res = 0
    i = 2
    while i*i <= n:
        while n%i == 0:
            n /= i
            count[i] += 1
        i += 1
    if n > 1: count[n] += 1
 
A,B = map(int,raw_input().split())
count = defaultdict(int)
for i in xrange(B+1,A+1): calc(i)
ans = 1
for i in count.values():
    ans = (ans*(i+1))%mod
print ans