#571935 (C) No.125 悪の花弁

• 問題: No.125 悪の花弁
• ユーザー: tails
• 提出日時: 2020-10-27 20:44:09
• 言語: C (gcc 13.3.0)
• 結果: AC
• 実行時間: 17 ms / 5,000 ms
• コード長: 1,562 bytes
• コンパイル時間: 1,284 ms
• コンパイル使用メモリ: 32,512 KB
• 実行使用メモリ: 10,208 KB
• 最終ジャッジ日時: 2024-07-21 22:02:41
• 合計ジャッジ時間: 1,348 ms
• ジャッジサーバーID （参考情報）: judge2 / judge5

ファイルパターン	結果
other	AC * 6

コンパイルメッセージ

main.c: In function 'main':
main.c:90:9: warning: implicit declaration of function 'printf' [-Wimplicit-function-declaration]
   90 |         printf("%d",CHMUL(ans,modinv_1000000007(N)));
      |         ^~~~~~
main.c:1:1: note: include '<stdio.h>' or provide a declaration of 'printf'
  +++ |+#include <stdio.h>
    1 | // original:
main.c:90:9: warning: incompatible implicit declaration of built-in function 'printf' [-Wbuiltin-declaration-mismatch]
   90 |         printf("%d",CHMUL(ans,modinv_1000000007(N)));
      |         ^~~~~~
main.c:90:9: note: include '<stdio.h>' or provide a declaration of 'printf'

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
// original:
// https://yukicoder.me/submissions/254947
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
char*mmap();
#define RD(v) int v=0;{int c;while(c=*rp++-48,c>=0)v=v*10+c;}
#define CHMUL(a,b) ((a)=(long)(a)*(b)%MOD)
#define MOD 1000000007
long modinv_1000000007(long a){
    long r=a;
#define A r=r*r%MOD*a%MOD
#define B r=r*r%MOD
    A;A;B;A;A;A;B;B;A;A;B;A;B;A;A;B;B;A;B;A;B;B;B;B;B;B;A;B;A;
#undef A
#undef B
    return r;
}
int fact[1000001],inv_fact[1000001];
void init_fact(int n) {
    long t;
    fact[0]=t=1;
    for (int i=0;++i<n;) {
        fact[i]=CHMUL(t,i);
    }
    inv_fact[n-1]=t=modinv_1000000007(fact[n-1]);
    for (int i=n-1;--i>=0;) {
        inv_fact[i]=CHMUL(t,i+1);
    }
}
int Euler_Phi(int n) {
    int res = n;
    for (int i = 2; i*i<=n; i++) {
        if (n % i == 0) {
            res -= res/i ;
            while (n /= i, n % i == 0);
        }
    }
    if (n != 1) res -= res/n;
    return res;
}
int divd[1000],divn;
void getdivisor(int n) {
    for (int i=1;i*i<=n;++i) {
        if (n%i == 0) {
            divd[divn++]=i;
            divd[divn++]=n/i;
        }
    }
    if(divn>=2 && divd[divn-1]==divd[divn-2]) --divn;
}
int c[100000];
int main() {
    char*rp=mmap(0l,1024l*1024,1,2,0,0ll);
    RD(K);
    int N=0;
    int GCD = 0;
    for(int i=0;i<K;++i) {
        RD(a);
        c[i]=a;
        N+=a;
        int t;
        while(t=a)a=GCD%t,GCD=t;
    }
    init_fact(N+1);
    getdivisor(GCD);
    int ans=0;
    for(int divi=0;divi<divn;++divi){
        int div=divd[divi];
        int ret = fact[N/div];
        for(int i=0;i<K;++i) {
            CHMUL(ret,inv_fact[c[i]/div]);
        }
        ans += CHMUL(ret,Euler_Phi(div));
        ans -= ans>=MOD?MOD:0;
    }
    printf("%d",CHMUL(ans,modinv_1000000007(N)));
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX