結果

問題 No.125 悪の花弁
コンテスト
ユーザー yaoshimax
提出日時 2015-04-16 01:19:46
言語 PyPy2
(7.3.20)
コンパイル:
pypy2 -m py_compile _filename_
実行:
/usr/bin/pypy2 Main.pyc
結果
AC  
実行時間 167 ms / 5,000 ms
コード長 1,085 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,384 ms
コンパイル使用メモリ 80,896 KB
実行使用メモリ 98,944 KB
最終ジャッジ日時 2026-03-25 22:33:52
合計ジャッジ時間 2,455 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 6
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

def inv(p,m):
    # return 1/p mod m , that is, return (a,b) s.t pa+bm = 1 (and get a)
    if p>m:
        b,a=inv(m,p)
        return (a,b)
    if p==1:
        return (1,0)
    # m=cp+r
    # pa+b(cp+r)=1 <=> (a+bc)p + br = 1
    c=m/p
    r=m%p
    b,a_bc=inv(r,p)
    return (a_bc-b*c, b)

def gcd(a,b):
    if b<a:
        return gcd(b,a)
    if b%a == 0:
        return a
    return gcd(b%a,a)

mod=1000000007
K=int(raw_input())
C=map(int,raw_input().split())
F=[1 for i in xrange(1000001)]
for i in xrange(1,1000001):
    F[i]=F[i-1]*i
    F[i]%=mod
g=C[0]
L=0
for c in C:
    g=gcd(g,c)
    L+=c

D=[i for i in range(1,g+1) if g%i==0]
Cnt=[0 for d in D]
ans=0
for i in xrange(len(D)-1,-1,-1):
    d=D[i]
    tCnt=F[L/d]
    #print F[L/d],
    for c in C:
        #print "/",F[c/d],
        tCnt*=inv(F[c/d],mod)[0]
        tCnt%=mod
    #print "=",tCnt
    Cnt[i]+=tCnt
    for j in xrange(i-1,-1,-1):
        if d%D[j]==0:
            Cnt[j]-=Cnt[i]
            Cnt[j]%=mod
    ans+=(Cnt[i]*inv(L/d,mod)[0])
    ans%=mod
#for c,d in zip(Cnt,D):
#    print L/d,":",c
print ans
0