글 읽기 - 왜 틀리는지 모르겠습니다.

ldhun041203 2년 전 0

밀러 라빈으로 해결했는데,

어디가 문제인지를 모르겠네요.

#include <iostream>

#include <algorithm>
#include <string>
#include <cstring>
#include <memory>
#include <cmath>

//data structure
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <utility>
#include <set>
#include <list>
#include <tuple>

#define INF 1e9+1
#define MAX
#define X first
#define Y second
#define MOD 1000000007

using namespace std;

typedef pair <int, int> pii;
typedef long long ll;
typedef pair <ll, ll> pll;

//--------struct,class-area



//---------variable-area

int N;

//---------function-area

ll P(ll a, ll n, ll mod) {
    ll ret = 1;
    a %= mod;
    while(n) {
        if (n & 1) ret = (ret * a) % mod;
        n /= 2;
        a = (a * a) % mod;
    }
    return ret;
}

bool MR(ll a, ll n) {
    if (a % n == 0) return true;
    ll k = n-1;
    while(true) {
        ll temp = P(a,k,n);
        if (temp == n-1) return true;
        if (k & 1) return (temp == 1 || temp == n-1);
        k /= 2;
    }
}


//---------end

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL); cout.tie(NULL);

//----------start

    cin >> N;
    int ans = N;

    while(N--) {
        ll A;
        cin >> A;

        A = 2*A+1;

        for (ll a : {2, 7, 61})
            if (!MR(a,A)) {
                ans--;
                break;
            }
    }

    cout << ans << endl;



//-----------end

    return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

왜 틀리는지 모르겠습니다.

ldhun041203 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말