自然数 k に対し、1 から k までの自然数のうち k と互いに素なものの個数を F(k) と定義します。 (F(k) はオイラーのΦ関数とも呼ばれています。参考:オイラーのφ関数(Wikipedia))
例えば F(12)=4 です。1 から 12 のうち 12 と互いに素なのは 1, 5, 7, 11 の 4 つです。
標準入力から、自然数 n(1 ≦ n ≦ 105)が与えられます。 標準出力に F(n!) を 1000003 で割った余りを出力するプログラムを書いてください。
例えば n=10 のとき、F(10!)=F(3628800)=829440 です。 同様に、F(20!) を 1000003 で割った値は 961998 です
求めるものはΦ(n!)でphi関数をバラすと n!Π_i (1-1/prime[i]) を計算すると (nまでの素数以外の積)(nまでの素数の積) とシンプルになるので、エラトステネスの篩でnまでの素数とそれ以外に分けて計算する。
def mark(s, x): for i in range(x + x, len(s), x): s[i] = False def sieve(n): s = [True] * n for x in range(2, int(n**0.5) + 1): if s[x]: mark(s, x) return [i for i in range(0,n) if s[i] and i > 1] N=int(input()) primes=sieve(N+1) not_primes=list(set(range(2,N+1))-set(sieve(N+1))) mod=1000003 res=1 for i in not_primes: res*=i res%=mod for i in primes: res*=i-1 res%=mod print(res%mod)