oj.uz

답안 #237657

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
237657 2020-06-08T07:06:07 Z Vimmer Sažetak (COCI17_sazetak) C++14
160 / 160
 9 ms 512 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")

#define F first
#define S second
#define sz(x) int(x.size())
#define pb push_back
#define N 100001
#define M ll(1e9 + 7)
#define inf 1e9 + 1e9

using namespace std;
//using namespace __gnu_pbds;

typedef long double ld;
typedef long long ll;
typedef short int si;
typedef array <int, 2> a2;

//typedef tree <int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

ll ans = 0, a[20], n, m;

ll lcm(ll x, ll y) {return min(ll(2e9), (x * y) / __gcd(x, y)); }

pair <ll, ll> gcd(ll a, ll b)
{
    if (a == 0) return {0, 1};

    pair <ll, ll> t = gcd(b % a, a);

    return {t.S - t.F * (b / a) ,t.F};
}

pair <ll, ll> calc(ll x, ll y)
{
    if (__gcd(x, y) != 1) return {-1, -1};

    ll Y = gcd(x, y).S;

    Y %= x;

    if (Y < 0) Y += x;

    return {Y * y, x * y};
}

void dfs(int v, int fr, int sd, int loc)
{
    if (v == m)
    {
        if (fr == 1 || sd == 1) return;

        pair <ll, ll> t = calc(fr, sd);

        if (t.F < 0 || t.F > n - 1) return;

        ans += loc * ((n - 1 - t.F) / t.S + 1);

        return;
    }

    dfs(v + 1, fr, sd, loc);

    dfs(v + 1, lcm(fr, a[v]), sd, -loc);

    dfs(v + 1, fr, lcm(a[v], sd), -loc);
}
int main()
{
    //freopen("input.txt", "r", stdin); //freopen("output4.txt", "w", stdout);

    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> m;

    for (int i = 0; i < m; i++) {cin >> a[i]; if (n % a[i] == 1) ans = 1;}

    dfs(0, 1, 1, 1);

    cout << ans << endl;
}

Subtask #1
160.0 / 160.0

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