Submission #342662

#	Time	Username	Problem	Language	Result	Execution time	Memory
342662		VodkaInTheJar	Sažetak (COCI17_sazetak)	C++14	128 / 160	1090 ms	364 KiB

sazetak

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define endl '\n'
     
using namespace std;
     
const int maxn = 5e6 + 3; 
const int maxm = 13;
     
long long n, m; 
long long k[maxm];
void read()
{
   cin >> n >> m;
   for (int i = 1; i <= m; i++)
   cin >> k[i];
}

int gcd(int a, int b)
{
	while (b)
	{
		int r = a % b;
		a = b;
		b = r;
	}
	
	return a; 
}

long long lcm(int a, int b)
{
	return 1ll * a * b / gcd(a, b);
}
     
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};
}

vector <pair <int, long long> > v;
int ans; 
void dfs(int pos, int cnt_bits, long long r, long long period)
{
	if (r > n-2)
	return;

	if (pos == (int)v.size())
	{
		if (cnt_bits == 0)
		return;
		
		if (cnt_bits & 1)
		ans += 1 + (n - 2 - r) / period; 
		
		else 
		ans -= 1 + (n - 2 - r) / period;
		
		return;
	}
	
	dfs(pos + 1, cnt_bits, r, period);
	
	if (r + period > n-2)
	{
		if (r % v[pos].first != v[pos].second)
		return;
		
		else 
		dfs(pos + 1, cnt_bits + 1, r, period);
		
		return;
	}
	
	int t = r - v[pos].second;
	int d = gcd(period, v[pos].first);
	
	if (t % d != 0)
	return;
	
	t /= d; 
	auto res = extended_euclid(v[pos].first / d, period / d);
	long long num = 1ll * res.first * t * v[pos].first + v[pos].second;
	long long nxt_period = lcm(period, v[pos].first);
	num %= nxt_period;
	if (num < 0)
	num += nxt_period;
	
	dfs(pos + 1, cnt_bits + 1, num, nxt_period);
}
     

void solve()
{
    for (int i = 1; i <= m; i++)
    if ((n - 1) % k[i] == 0)
    {
    	ans++;
    	break;
    }
    
    n++;
    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;
    }
    
    dfs(0, 0, 0, 1);
    
    cout << ans << endl; 
}
     
int main()
{
    ios_base::sync_with_stdio(false);
   	cin.tie(nullptr);
    cout.tie(nullptr);
     
    read();
    solve();
}

• Subtask 1: 128 / 160