oj.uz

답안 #342677

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
342677 2021-01-02T16:02:36 Z VodkaInTheJar Sažetak (COCI17_sazetak) C++14
160 / 160
 13 ms 492 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define endl '\n'
     
using namespace std;
     
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];
}

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

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

long long ans = 0;
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-2 || lcm2 > n-2)
			{
				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;
		
		long long to_add = 0;
		if (r <= n-2)
		to_add = 1 + (n-2-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
160.0 / 160.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 2 ms 364 KB Output is correct
9 Correct 8 ms 364 KB Output is correct
10 Correct 13 ms 364 KB Output is correct