oj.uz

Submission #26627

# Submission time Handle Problem Language Result Execution time Memory
26627 2017-07-03T13:30:21 Z model_code Strongbox (POI11_sej) C++14
100 / 100
 386 ms 4532 KB 
/*************************************************************************
 *                                                                       *
 *                    XVIII Olimpiada Informatyczna                      *
 *                                                                       *
 *   Zadanie:           Sejf                                             *
 *   Autor:             Tomasz Kociumaka                                 *
 *   Zlozonosc czasowa: O(sqrt(n)+k*log(n))                              *
 *   Opis:              Rozwiazanie wzorcowe                             *
 *                      proste szukanie dzielnikow, faktoryzacja bez     *
 *                      optymalizacji, korzysta z mapy z STL             *
 *                                                                       *
 *************************************************************************/

#include <cstdio>
#include <vector>
#include <map>

#define REP(a,n) for (int a=0; a<(n); ++a)
#define FOR(a,b,c) for (int a=(b); a<=(c); ++a)
#define FORD(a,b,c) for (int a=(b); a>=(c); --a)
#define FORE(i, cnt) for(__typeof((cnt).begin()) i = (cnt).begin(); i != (cnt).end(); ++i)
#define FORED(i, cnt) for(__typeof((cnt).rbegin()) i = (cnt).rbegin(); i != (cnt).rend(); ++i)
#define MP make_pair
#define PB push_back

using namespace std;

typedef long long LL;

template<class T> 
inline int size(const T &t) { return t.size(); }


LL gcd(LL a, LL b) {
    while(b != 0) {
        a %= b;
        swap(a,b);
    }
    return a;
}

vector<LL> dvs; //dzielniki
vector<LL> pDvs; //dzielniki pierwsze


void computeDivisors(LL n) { //oblicza dvs i pDvs w czasie O(sqrt(n))
    LL m  = n; //do obliczania pDiv
    dvs.PB(1);
    for (int d = 2; d*(LL)d <= n; ++d) { //dzielniki mniejsze niz sqrt(n)
        if (n%d == 0) {
            dvs.PB(d);
            if (m%d == 0) {
                pDvs.PB(d);
                do m/=d; while (m%d == 0);
            }
        }
    }
    //i pozostale
    if (m != 1) pDvs.PB(m);
    int i = size(dvs) - 1;
    if (dvs[i]*dvs[i] == n) --i; //nie wstawiaj sqrt(n) dwa razy
    for (; i >= 0; --i) dvs.PB(n/dvs[i]);
}

int main() {
    LL n;
    int k;
    LL *m;
    scanf("%lld%d", &n, &k);
    m = new LL[k];
    REP(i, k) {
        scanf("%lld", &m[i]);
        m[i] = gcd(m[i], n);
    }
    computeDivisors(n);

    map<LL, bool> good; //czy dzielnik nie dzieli zadnej z liczb m_i
    FORE(it, dvs) good[*it] = true;
    REP(i,k - 1) good[m[i]] = false;

    LL best = -1; //najlepszy dotychczas znaleziony wynik

    //sprawdzaj od gory dzielniki
    FORED(it, dvs) {
        if (!good[*it]) continue;
        FORE(jt, pDvs) {
            if ((n / (*it)) % (*jt) != 0) continue; //tak napisane nie spowoduje overflowa
            if (!good[*it * (*jt)]) {
                good[*it] = false;
                break;
            }
        }
        if (good[*it] && m[k-1] % (*it) == 0) {
            best = max(best, n / (*it));
        }
    }
    printf("%lld\n",best);
    delete[] m;
    return 0;
}

Compilation message

sej.cpp: In function 'int main()':
sej.cpp:69:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld%d", &n, &k);
                            ^
sej.cpp:72:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld", &m[i]);
                             ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1184 KB Output is correct
2 Correct 0 ms 1184 KB Output is correct
3 Correct 0 ms 1184 KB Output is correct
4 Correct 0 ms 1184 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1184 KB Output is correct
2 Correct 0 ms 1184 KB Output is correct
3 Correct 0 ms 1184 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1184 KB Output is correct
2 Correct 0 ms 1316 KB Output is correct
3 Correct 0 ms 1316 KB Output is correct

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1184 KB Output is correct
2 Correct 3 ms 1328 KB Output is correct
3 Correct 3 ms 1328 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1184 KB Output is correct
2 Correct 23 ms 1724 KB Output is correct
3 Correct 13 ms 1184 KB Output is correct
4 Correct 19 ms 1724 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 1184 KB Output is correct
2 Correct 129 ms 2324 KB Output is correct
3 Correct 153 ms 1184 KB Output is correct
4 Correct 129 ms 2324 KB Output is correct

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 1184 KB Output is correct
2 Correct 143 ms 2324 KB Output is correct
3 Correct 169 ms 1184 KB Output is correct
4 Correct 99 ms 2192 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 1184 KB Output is correct
2 Correct 153 ms 2324 KB Output is correct
3 Correct 123 ms 1184 KB Output is correct
4 Correct 119 ms 2324 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 1184 KB Output is correct
2 Correct 153 ms 2584 KB Output is correct
3 Correct 139 ms 1184 KB Output is correct
4 Correct 169 ms 2324 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 1184 KB Output is correct
2 Correct 123 ms 1184 KB Output is correct
3 Correct 123 ms 1184 KB Output is correct
4 Correct 143 ms 2324 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 1968 KB Output is correct
2 Correct 203 ms 3360 KB Output is correct
3 Correct 196 ms 3360 KB Output is correct
4 Correct 259 ms 3744 KB Output is correct
5 Correct 249 ms 3364 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 2748 KB Output is correct
2 Correct 326 ms 4140 KB Output is correct
3 Correct 236 ms 3716 KB Output is correct
4 Correct 219 ms 3540 KB Output is correct
5 Correct 286 ms 4112 KB Output is correct

Subtask #13
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 3140 KB Output is correct
2 Correct 386 ms 4532 KB Output is correct
3 Correct 349 ms 4464 KB Output is correct
4 Correct 303 ms 4496 KB Output is correct
5 Correct 336 ms 4528 KB Output is correct

Subtask #14
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 3140 KB Output is correct
2 Correct 353 ms 4532 KB Output is correct
3 Correct 326 ms 4272 KB Output is correct
4 Correct 306 ms 4532 KB Output is correct
5 Correct 303 ms 4524 KB Output is correct