結果

問題 No.125 悪の花弁
ユーザー yaoshimaxyaoshimax
提出日時 2015-04-16 01:19:46
言語 PyPy2
(7.3.15)
結果
AC  
実行時間 250 ms / 5,000 ms
コード長 1,085 bytes
コンパイル時間 1,657 ms
コンパイル使用メモリ 77,060 KB
実行使用メモリ 96,080 KB
最終ジャッジ日時 2024-07-04 14:47:30
合計ジャッジ時間 3,180 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 115 ms
85,632 KB
testcase_01 AC 190 ms
95,688 KB
testcase_02 AC 250 ms
96,080 KB
testcase_03 AC 222 ms
96,000 KB
testcase_04 AC 101 ms
84,560 KB
testcase_05 AC 103 ms
85,716 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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