oj.uz

Submission #342324

# Submission time Handle Problem Language Result Execution time Memory
342324 2021-01-01T22:00:43 Z VodkaInTheJar Sažetak (COCI17_sazetak) C++14
144 / 160
 500 ms 364 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define endl '\n'

using namespace std;

const int maxn = 5e6 + 3; 
const int maxm = 13;

int n, m; 
int k[maxm];
void read()
{
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	cin >> k[i];
}

pair <long long, long long> extended_euclid(int a, int b)
{
	if (b == 0)
	return {1, 0};
	
	int r = a % b, q = a / b; 
	auto res = extended_euclid(b, r);
	
	return {res.second, res.first - 1ll * res.second * q};
}

bool dp[maxn];
void solve()
{
	int ans = 0;
	for (int i = 1; i <= m; i++)
	if ((n - 1) % k[i] == 0)
	{
		ans++;
		break;
	}
	
	n++;
	set <long long> s;
	vector <pair <long long, long long> > v;
	for (int i = 1; i <= m; i++)
	for (int j = 1; j <= m; j++)
	if (__gcd(k[i], k[j]) == 1)
	{
		long long period = 1ll * k[i] * k[j];
		auto sol = extended_euclid(k[j], k[i]);
		
		long long num = sol.second * k[i];
		num %= period;
		if (num < 0)
		num += period;
		
		if (num > n-2)
		continue;
		
		v.push_back({period, num});
	}
	
	if (v.empty())
	{
		cout << ans << endl;
		return;
	}
	
	sort (v.begin(), v.end());
	ans += 1 + (n-2-v[0].second) / v[0].first;
	
	for (int i = 1; i < (int)v.size(); i++)
	{
		long long curr = v[i].second;
		while (curr <= n-2)
		{
			bool can = false;
			for (int j = 0; j < i; j++)
			if (curr % v[j].first == v[j].second)
			{
				can = true;
				break;
			}
			
			if (!can)
			ans++;
			
			curr += v[i].first;
		}
	}
	
	cout << ans << endl; 
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	read();
	solve();
}

Subtask #1
144.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 11 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 3 ms 364 KB Output is correct
7 Correct 15 ms 364 KB Output is correct
8 Correct 119 ms 364 KB Output is correct
9 Execution timed out 1070 ms 364 KB Time limit exceeded
10 Correct 1 ms 364 KB Output is correct