結果

問題 No.125 悪の花弁
ユーザー tailstails
提出日時 2020-10-27 20:44:09
言語 C
(gcc 12.3.0)
結果
AC  
実行時間 17 ms / 5,000 ms
コード長 1,562 bytes
コンパイル時間 1,084 ms
コンパイル使用メモリ 31,444 KB
実行使用メモリ 10,304 KB
最終ジャッジ日時 2023-09-29 03:24:56
合計ジャッジ時間 2,244 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 10 ms
9,560 KB
testcase_01 AC 12 ms
10,108 KB
testcase_02 AC 16 ms
10,244 KB
testcase_03 AC 17 ms
10,304 KB
testcase_04 AC 14 ms
9,600 KB
testcase_05 AC 13 ms
9,576 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: 関数 ‘main’ 内:
main.c:90:9: 警告: 関数 ‘printf’ の暗黙的な宣言です [-Wimplicit-function-declaration]
   90 |         printf("%d",CHMUL(ans,modinv_1000000007(N)));
      |         ^~~~~~
main.c:1:1: 備考: include ‘<stdio.h>’ or provide a declaration of ‘printf’
  +++ |+#include <stdio.h>
    1 | // original:
main.c:90:9: 警告: 組み込み関数 ‘printf’ の互換性がない暗黙的な宣言です [-Wbuiltin-declaration-mismatch]
   90 |         printf("%d",CHMUL(ans,modinv_1000000007(N)));
      |         ^~~~~~
main.c:90:9: 備考: include ‘<stdio.h>’ or provide a declaration of ‘printf’

ソースコード

diff # 

// 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)));
}
0