TopCoder SRM 652 Div1 o-- 1283->1283

276th, 141.78pts, +0/-0 challenge
Volatility: 324->324

SRM 652 - Togetterまとめ

久しぶりに参加したら、途中でサンプルアウトプットが変わったり、いくつもアナウンスが流れるドタバタした感じだった
前回に引き続き今回もunratedになってしまったぽいので、unratedジャンケンに勝利してしまった

ジャンケンをしてunratedになったら勝ち

— 無限猿(id:sucrose)@15月病 (@Scaled_Wurm) 2015, 3月 9

250: ThePermutationGame

問題文の意味がわからずに途中で寝ようかと思った

\(1\)から\(N\)の数列の順列を\(p\)としたときに、関数が\(f(m) = p[f(m-1)]\)、ただし\(f(1) = p[1]\)と定義される
このとき、どんな順列\(p\)に対しても\(f(x) = 1\)となるような最小の\(x\)を求める
ただし\(1 \le N \le 100000\)

\(1\)から\(N\)回のそれぞれで一巡する順列が作れるので、それらの数についての最小公倍数を求めればよい
\(N\)以下の素数の累乗についてのみ考えてかけていけば計算できる

# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect

def eratosthenes_sieve(n):
    table = [0] * (n + 1)
    prime_list = []
    
    for i in xrange(2, n + 1):
        if table[i] == 0:
            prime_list.append(i)
            for j in xrange(i + i, n + 1, i):
                table[j] = 1
    
    return prime_list

class ThePermutationGame:
    def findMin(self, N):
        primes = eratosthenes_sieve(N + 3)
        
        result = 1
        for p in primes:
            temp = p
            while temp <= N:
                if temp * p > N:
                    result = result * temp % 1000000007
                    break
                temp *= p
        return result % 1000000007