結果

問題 No.917 Make One With GCD
ユーザー startcppstartcpp
提出日時 2019-10-26 16:01:26
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 1,023 bytes
コンパイル時間 991 ms
コンパイル使用メモリ 68,828 KB
実行使用メモリ 4,376 KB
最終ジャッジ日時 2023-10-12 11:24:07
合計ジャッジ時間 2,614 ms
ジャッジサーバーID
(参考情報)
judge15 / judge14
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 AC 1 ms
4,348 KB
testcase_02 AC 1 ms
4,348 KB
testcase_03 AC 1 ms
4,352 KB
testcase_04 AC 1 ms
4,356 KB
testcase_05 WA -
testcase_06 AC 7 ms
4,352 KB
testcase_07 WA -
testcase_08 AC 3 ms
4,348 KB
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 AC 2 ms
4,348 KB
testcase_18 WA -
testcase_19 AC 1 ms
4,352 KB
testcase_20 AC 2 ms
4,348 KB
testcase_21 AC 2 ms
4,348 KB
testcase_22 AC 2 ms
4,372 KB
testcase_23 WA -
testcase_24 AC 2 ms
4,352 KB
testcase_25 WA -
testcase_26 AC 1 ms
4,352 KB
testcase_27 AC 2 ms
4,348 KB
testcase_28 AC 2 ms
4,348 KB
testcase_29 AC 1 ms
4,352 KB
testcase_30 AC 1 ms
4,352 KB
testcase_31 AC 2 ms
4,352 KB
testcase_32 AC 2 ms
4,352 KB
testcase_33 AC 1 ms
4,348 KB
testcase_34 AC 2 ms
4,352 KB
testcase_35 AC 2 ms
4,348 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

#include <iostream>
#include <algorithm>
#include <vector>
#define rep(i, n) for(i = 0; i < n; i++)
using namespace std;

int n;
int a[50];

int main() {
	int i, j;
	
	cin >> n;
	rep(i, n) cin >> a[i];
	
	vector<int> yakus;
	rep(i, n) {
		for (j = 1; j * j <= a[i]; j++) {
			if (a[i] % j == 0) {
				yakus.push_back(j);
				if (j != a[i] / j) {
					yakus.push_back(a[i] / j);
				}
			}
		}
	}
	sort(yakus.begin(), yakus.end());
	yakus.erase(unique(yakus.begin(), yakus.end()), yakus.end());
	
	vector<int> F;	//F[i] = gcdがyakus[i]の倍数になる部分列の個数
	rep(i, yakus.size()) {
		int cnt = 0;
		rep(j, n) {
			if (a[j] % yakus[i] == 0) {
				cnt++;
			}
		}
		F.push_back((1LL << cnt) - 1);
	}
	
	vector<int> G;	//G[i] = gcdがちょうどyakus[i]になる部分列の個数
	G.resize(yakus.size());
	
	for (i = yakus.size() - 1; i >= 0; i--) {
		G[i] = F[i];
		for (j = i + 1; j < yakus.size(); j++) {
			if (yakus[j] % yakus[i] == 0) {
				G[i] -= G[j];
			}
		}
	}
	
	cout << G[0] << endl;
	return 0;
}
0