結果

問題 No.917 Make One With GCD
ユーザー startcppstartcpp
提出日時 2019-10-26 16:02:04
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 13 ms / 2,000 ms
コード長 1,048 bytes
コンパイル時間 650 ms
コンパイル使用メモリ 68,096 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-24 11:09:08
合計ジャッジ時間 1,728 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

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

int n;
int a[50];

signed 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