結果

問題 No.917 Make One With GCD
ユーザー startcppstartcpp
提出日時 2019-10-26 16:02:06
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 13 ms / 2,000 ms
コード長 1,048 bytes
コンパイル時間 638 ms
コンパイル使用メモリ 68,804 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-24 11:08:56
合計ジャッジ時間 1,746 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

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