제출 #342670

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
342670		VodkaInTheJar	Sažetak (COCI17_sazetak)	C++14	128 / 160	10 ms	364 KiB

sazetak

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define endl '\n'
     
using namespace std;
     
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];
}

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};
}

int ans;   
void solve()
{
	/*
    for (int i = 1; i <= m; i++)
    if ((n - 1) % k[i] == 0)
    {
    	ans++;
    	break;
    }
    */
    
    for (int i = 1; i < (1 << m); i++)
    for (int j = 1; j < (1 << m); j++)
    {
		bool is = false;
		for (int p = 0; p < m; p++)
		if ((i & (1 << p)) && (j & (1 << p)))
		{
			is = true;
			break;
		}
		
		if (is)
		continue;
		
	    is = false;
	    long long lcm1 = 1, lcm2 = 1; 
	    for (int p = 0; p < m; p++)
	    {
			if (lcm1 > n-1 || lcm2 > n-1)
			{
				is = true;
				break;
			}
			
			if (i & (1 << p))
			lcm1 = lcm(lcm1, k[p+1]); 
			
			if (j & (1 << p))
			lcm2 = lcm(lcm2, k[p+1]);
		}
		
		if (is || gcd(lcm1, lcm2) > 1)
		continue;
		
		auto res = extended_euclid(lcm2, lcm1);
		long long period = lcm1 * lcm2; 
		long long r = -res.second * lcm1;
		r %= period;
		
		if (r < 0)
		r += period;
		
		int to_add = 0;
		if (r <= n-1)
		to_add = 1 + (n-1-r) / period;
		
		int cnt_bits = __builtin_popcount(i) + __builtin_popcount(j);
		if (cnt_bits % 2 == 0)
		ans += to_add;
		
		else 
		ans -= to_add;
	}
	
	cout << ans << endl; 
}
     
int main()
{
    ios_base::sync_with_stdio(false);
   	cin.tie(nullptr);
    cout.tie(nullptr);
     
    read();
    solve();
}

• Subtask 1: 128 / 160