結果

問題 No.2620 Sieve of Coins
コンテスト
ユーザー startcpp
提出日時 2023-12-15 00:55:26
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 236 ms / 2,000 ms
コード長 8,682 bytes
コンパイル時間 1,843 ms
コンパイル使用メモリ 123,928 KB
実行使用メモリ 19,236 KB
最終ジャッジ日時 2024-09-27 05:52:28
合計ジャッジ時間 6,793 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 53
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

mt19937_64 mt(23490832);
vector<int> generate(int L, int N) {
	vector<int> p2, p3;
	p2.push_back(1); while (*p2.rbegin() <= L) p2.push_back(*p2.rbegin() * 2);
	p3.push_back(1); while (*p3.rbegin() <= L) p3.push_back(*p3.rbegin() * 3);
	
	vector<int> s;
	for (int i = 0; p2[i] <= L; i++) {
		for (int j = 0; p2[i] * p3[j] <= L; j++) {
			s.push_back(p2[i] * p3[j]);
		}
	}
	sort(s.begin(), s.end());

	vector<bool> used(s.size(), false);
	vector<int> a;
	for (int i = 0; i < N; i++) {
		int r; do { r = mt() % s.size(); } while (used[r]);
		used[r] = true;
		a.push_back(s[r]);
	}
	sort(a.begin(), a.end());
	return a;
}

vector<int> generateSmallest(int L, int N) {
	vector<int> p2, p3;
	p2.push_back(1); while (*p2.rbegin() <= L) p2.push_back(*p2.rbegin() * 2);
	p3.push_back(1); while (*p3.rbegin() <= L) p3.push_back(*p3.rbegin() * 3);
	vector<int> s;
	for (int i = 0; p2[i] <= L; i++) {
		for (int j = 0; p2[i] * p3[j] <= L; j++) {
			s.push_back(p2[i] * p3[j]);
		}
	}
	sort(s.begin(), s.end());
	s.resize(N);
	return s;
}

int subtask1(int L, int N, vector<int> a) {
	int i, j;
	vector<bool> isOmote(L + 1, false);
	rep(i, N) isOmote[a[i]] = true;
	int ret = 0;
	for (i = 1; i <= L; i++) {
		if (isOmote[i]) {
			ret++;
			for (j = 2 * i; j <= L; j += i) isOmote[j] = !isOmote[j];
		}
	}
	return ret;
}

pair<vector<bool>, vector<int>> setPrimeMebius(int n) {
	vector<bool> isPrime(n + 1, true);
	vector<int> mebius(n + 1, 1);
	isPrime[0] = isPrime[1] = false;
	for (int i = 2; i <= n; i++) {
		if (isPrime[i]) {
			mebius[i] *= -1;
			int cnt = 2; if (i == 2) cnt = 0;
			for (int j = 2 * i; j <= n; j += i) {
				isPrime[j] = false;
				if (cnt == 0) { mebius[j] = 0; }
				else { mebius[j] *= -1; }
				cnt++; if (cnt == i) cnt = 0;
			}
		}
	}
	return pair<vector<bool>, vector<int>>(isPrime, mebius);
}

int gcd(int a, int b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}

//subtask2_1, subtask2_2は、Σ|mebius(i)| (1≦i≦L) を返す. これはL=1,N=1,A={1}のときの答え。
//subtask2_1: 約数包除 O(√Llog√L), subtask2_2: メビウス関数を使った計算 O(√L)
int subtask2_1(int L) { //sqL = floor(√L)
	int i, j;
	int sqL; for (sqL = 1; sqL * sqL <= L; sqL++); sqL--;
	vector<int> cnts(sqL + 1); //cnts[m]: L以下のm^2の正の倍数であって、x>mについてx^2の倍数でないものの個数

	for (i = sqL; i >= 1; i--) {
		cnts[i] = L / (i * i);
		for (j = 2 * i; j <= sqL; j += i) cnts[i] -= cnts[j];
	}
	return cnts[1];
}

int subtask2_2(int L, vector<int> &mebius) {
	int ret = 0;
	for (int i = 1; i * i <= L; i++) {
		ret += mebius[i] * (L / (i * i));
	}
	return ret;
}

int calc3_naive(int L, bool noDiv2, bool noDiv3) {
	int i, j;
	vector<bool> isOmote(L + 1, false);
	isOmote[1] = true;
	int ret = 0;
	for (i = 1; i <= L; i++) {
		if (isOmote[i]) {
			for (j = 2 * i; j <= L; j += i) isOmote[j] = !isOmote[j];
			if (!((noDiv2 && i % 2 == 0) || (noDiv3 && i % 3 == 0))) ret++;
		}
	}
	return ret;
}

int loopCount = 0;
int calc3_fast(int L, bool noDiv2, bool noDiv3, vector<int> &mebius) {
	int ret = 0;
	for (int i = 1; i * i <= L; i++) {
		loopCount++;
		int keisu;
		if (i % 2 == 0 && noDiv2) keisu = 0;
		else if (i % 3 == 0 && noDiv3) keisu = 0;
		else {
			int c = L / (i * i);
			keisu = c;
			if (noDiv2) keisu -= c / 2;
			if (noDiv3) keisu -= c / 3;
			if (noDiv2 && noDiv3) keisu += c / 6;
		}
		ret += mebius[i] * keisu;
	}
	return ret;
}

string binaryStr(int x, int d) {
	string s;
	for (int i = d - 1; i >= 0; i--) s += ((x >> i) % 2) + '0';
	return s;
}

int subtask3(int L, vector<int> &a, vector<int> &mebius) {
	int n = a.size();
	vector<int> div2(n), div3(n);
	int i, j;
	rep(i, n) {
		int t = a[i];
		div2[i] = div3[i] = 0;
		while (t % 2 == 0) { t /= 2; div2[i]++; }
		while (t % 3 == 0) { t /= 3; div3[i]++; }
	}

	int ret = 0;
	rep(i, (1 << n)) {
		int l2 = -1, r2 = 1e+6, l3 = -1, r3 = 1e+6;	//2^[l2, r2] * 3^[l3, r3] * 5^[0, 1] * 7 * [0, 1] * .... の形が表
		int bitCount = 0;
		rep(j, n) {
			if ((i >> j) % 2) {
				l2 = max(l2, div2[j]);
				r2 = min(r2, div2[j] + 1);
				l3 = max(l3, div3[j]);
				r3 = min(r3, div3[j] + 1);
				bitCount++;
			}
		}
		if (bitCount == 0 || l2 > r2 || l3 > r3) continue;
		int tmpL = L;
		rep(j, l2) tmpL /= 2;
		rep(j, l3) tmpL /= 3;
		if (tmpL == 0) continue;
		bool noDiv2 = (l2 == r2);
		bool noDiv3 = (l3 == r3);
		int res = calc3_fast(tmpL, noDiv2, noDiv3, mebius);
		//cerr << "[subtask3] i: " << binaryStr(i, n) << ", l2: " << l2 << ", r2: " << r2 << ", l3: " << l3 << ", r3: " << r3 << ", tmpL: " << tmpL << ", res: " << res << endl;
		if (bitCount % 2 == 1) ret += res * (1LL << (bitCount - 1));
		else ret -= res * (1LL << (bitCount - 1));
	}
	return ret;
}

int subtask4(int L, vector<int> &a, vector<int> &mebius) {
	int n = a.size();
	bool plot[60][60] = {false};
	int i, j;
	rep(i, n) {
		int c2 = 0, c3 = 0, t = a[i];
		while (t % 2 == 0) { t /= 2; c2++; }
		while (t % 3 == 0) { t /= 3; c3++; }
		plot[c2][c3] = true;
	}
	vector<int> p2, p3;
	p2.push_back(1);
	p3.push_back(1);
	while (*p2.rbegin() <= L || p2.size() < 4) p2.push_back(*p2.rbegin() * 2);
	while (*p3.rbegin() <= L) p3.push_back(*p3.rbegin() * 3);
	typedef tuple<int, bool, bool> T;
	map<T, int> mp;

	int ret = 0;
	for (i = 0; p2[i] <= L; i++) {
		for (j = 0; p2[i] * p3[j] <= L; j++) {
			//選ぶ要素のlcmが2^i * 3^jになる場合について数える
			int tmpL = L / (p2[i] * p3[j]);
			for (int k = 0; k < 16; k++) {
				int l;
				int max2 = -1, min2 = 1e+6, max3 = -1, min3 = 1e+6, cnt = 0;
				rep(l, 4) {
					if ((k >> l) & 1) {
						int c2 = i - l / 2;
						int c3 = j - l % 2;
						if (c2 < 0 || c3 < 0 || plot[c2][c3] == false) break;
						max2 = max(max2, c2);
						min2 = min(min2, c2);
						max3 = max(max3, c3);
						min3 = min(min3, c3);
						cnt++;
					}
				}
				if (l < 4 || cnt == 0 || max2 != i || max3 != j) continue;
				bool noDiv2 = (min2 != max2);
				bool noDiv3 = (min3 != max3);
				T key = T(tmpL, noDiv2, noDiv3);
				if (mp.find(key) == mp.end()) {
					mp[key] = calc3_fast(tmpL, noDiv2, noDiv3, mebius);
				}
				int res = mp[key];
				if (cnt % 2 == 1) { ret += res * p2[cnt - 1]; }
				else { ret -= res * p2[cnt - 1]; }
			}
		}
	}
	return ret;
}

void spec_calc3(int maxL) {
	int sqL; for (sqL = 1; sqL * sqL <= maxL; sqL++); sqL--;
	auto prime_mebius = setPrimeMebius(sqL);
	vector<int> mebius = prime_mebius.second;
	for (int L = 1; L <= maxL; L++) {
		for (int noDiv2 = 0; noDiv2 <= 1; noDiv2++) {
			for (int noDiv3 = 0; noDiv3 <= 1; noDiv3++) {
				int res1 = calc3_naive(L, noDiv2 == 1, noDiv3 == 1);
				int res2 = calc3_fast(L, noDiv2 == 1, noDiv3 == 1, mebius);
				if (res1 != res2) {
					cout << "[WA] L: " << L << ", noDiv2: " << noDiv2 << ", noDiv3: " << noDiv3 << endl;
					cout << "naive: " << res1 << ", ret: " << res2 << endl;
					return;
				}
			}
		}
	}
	cout << "Correct" << endl;
}

void spec_main() {
	int L; cin >> L;
	int N; cin >> N;
	int sqL; for (sqL = 1; sqL * sqL <= L; sqL++); sqL--;
	auto prime_mebius = setPrimeMebius(sqL);
	vector<int> mebius = prime_mebius.second;
	for (int t = 0; t < 100; t++) {
		vector<int> a = generate(L, N);
		int res1 = subtask1(L, N, a);
		int res2 = subtask4(L, a, mebius);
		if (res1 != res2) {
			cout << "WA[" << t << "] L: " << L << ", N: " << N << endl;
			for (int i = 0; i < a.size(); i++) cout << a[i] << " "; cout << endl;
			cout << "naive: " << res1 << ", ans: " << res2 << endl;
			subtask4(L, a, mebius);	//デバッグする
			return;
		}
	}
	cout << "Correct" << endl;
}

void spec_speed() {
	int L; cin >> L;
	int N; cin >> N;
	vector<int> a = generateSmallest(L, N);
	int i; rep(i, a.size()) cout << a[i] << " "; cout << endl;
	clock_t start = clock();
	int sqL; for (sqL = 1; sqL * sqL <= L; sqL++); sqL--;
	auto prime_mebius = setPrimeMebius(sqL);
	vector<int> mebius = prime_mebius.second;
	int res = subtask4(L, a, mebius);
	cout << (clock() - start) / (double)CLOCKS_PER_SEC << "[sec]" << endl;
	cout << res << endl;
	cout << "loopCount: " << loopCount << endl;
}

void run_solver() {
	int L, N; cin >> L >> N;
	vector<int> a;
	int i;
	rep(i, N) { int x; cin >> x; a.push_back(x); }
	assert(L <= 1000000000000);
	assert(N <= 534);
	rep(i, N - 1) { assert(a[i] < a[i + 1]); }
	int sqL = 1; while (sqL * sqL <= L) sqL++; sqL--;
	auto prime_mebius = setPrimeMebius(sqL);
	vector<int> mebius = prime_mebius.second;
	int res = subtask4(L, a, mebius);
	cout << res << endl;
}

signed main() {
	run_solver();
	return 0;
}
0