結果
| 問題 | No.3030 ミラー・ラビン素数判定法のテスト |
| ユーザー |
 kacho65535
|
| 提出日時 | 2020-11-15 20:21:59 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 149 ms / 9,973 ms |
| コード長 | 7,273 bytes |
| コンパイル時間 | 2,570 ms |
| コンパイル使用メモリ | 188,252 KB |
| 実行使用メモリ | 5,248 KB |
| 最終ジャッジ日時 | 2024-11-16 23:33:55 |
| 合計ジャッジ時間 | 3,538 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
5,248 KB |
| testcase_01 | AC | 2 ms
5,248 KB |
| testcase_02 | AC | 2 ms
5,248 KB |
| testcase_03 | AC | 2 ms
5,248 KB |
| testcase_04 | AC | 80 ms
5,248 KB |
| testcase_05 | AC | 74 ms
5,248 KB |
| testcase_06 | AC | 22 ms
5,248 KB |
| testcase_07 | AC | 22 ms
5,248 KB |
| testcase_08 | AC | 22 ms
5,248 KB |
| testcase_09 | AC | 149 ms
5,248 KB |
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:281:15: warning: 'X' may be used uninitialized [-Wmaybe-uninitialized]
281 | if (MR(X))
| ~~^~~
main.cpp:279:12: note: 'X' was declared here
279 | ll X;
| ^
main.cpp:275:8: warning: 'Q' may be used uninitialized [-Wmaybe-uninitialized]
275 | ll Q;
| ^
ソースコード
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx")
#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
using ll = long long;
#define mod 1000000007ll
#define loop(i, n) for (int i = 0; i < n; i++)
#define flagcount(bit) __builtin_popcount(bit)
#define flag(x) (1ll << x)
#define flagadd(bit, x) bit |= flag(x)
#define flagpop(bit, x) bit &= ~flag(x)
#define flagon(bit, i) bit &flag(i)
#define flagoff(bit, i) !(bit & (1ll << i))
#define all(v) v.begin(), v.end()
#define putout(a) cout << a << '\n'
template <typename T>
bool chmax(T &a, const T &b)
{
if (a < b)
{
a = b; // aをbで更新
return true;
}
return false;
}
template <typename T>
bool chmin(T &a, const T &b)
{
if (a > b)
{
a = b; // aをbで更新
return true;
}
return false;
}
void AS(ll X, ll L, ll R) { assert(L <= X && X <= R); }
template <typename T>
bool primejudge(T n)
{
if (n < 2)
return false;
else if (n == 2)
return true;
else if (n % 2 == 0)
return false;
double sqrtn = sqrt(n);
for (T i = 3; i < sqrtn + 1; i++)
{
if (n % i == 0)
{
return false;
}
i++;
}
return true;
}
//modかけ算
inline ull modd(ull a, ull m)
{
return (a % m + m) % m;
}
unsigned long long mul(unsigned long long a, unsigned long long b, unsigned long long p) {
long long ret = a * b - p * (unsigned long long)((long double)(a) * (long double)(b) / (long double)(p));
return ret + p * (ret < 0) - p * (ret >= (long long)p);
}
//modpow
ull modp(ull a, ull n, ull p)
{
ull res = 1;
while (n > 0)
{
if (n & 1)
res = mul(res, a, p);
a = mul(a, a, p);
n >>= 1ll;
}
return res;
}
//素数ならtrue,合成数ならfalseを返す
bool MR(ull X)
{
if (X < 10000)
return primejudge(X);
if (X % 2 == 0)
return false;
ull Z = X - 1;
ull s = 0, t = 0;
while (Z % 2 == 0)
{
s++;
Z /= 2;
}
t = Z;
vector<ull> A = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
for (auto a : A)
{
bool ok = true;
if (modp(a, t, X) == 1)
{
ok = false;
continue;
}
ll Z = modp(a, t, X);
for (ull i = 0; i < s; i++)
{
if (Z == X - 1)
{
ok = false;
break;
}
Z %= X;
Z = mul(Z, Z, X);
}
if (ok)
{
return false; //条件を満たすものが存在しなかった
}
}
return true;
}
static struct IO
{
char tmp[1 << 10];
// fast input routines
char cur;
//#define nextChar() (cur = getc_unlocked(stdin))
//#define peekChar() (cur)
inline char nextChar() { return cur = getc_unlocked(stdin); }
inline char peekChar() { return cur; }
inline operator bool() { return peekChar(); }
inline static bool isBlank(char c) { return (c < '!' && c); }
inline bool skipBlanks()
{
while (isBlank(nextChar()))
;
return peekChar() != 0;
}
inline IO &operator>>(char &c)
{
c = nextChar();
return *this;
}
inline IO &operator>>(char *buf)
{
if (skipBlanks())
{
if (peekChar())
{
*(buf++) = peekChar();
while (!isBlank(nextChar()))
*(buf++) = peekChar();
}
*(buf++) = 0;
}
return *this;
}
inline IO &operator>>(string &s)
{
if (skipBlanks())
{
s.clear();
s += peekChar();
while (!isBlank(nextChar()))
s += peekChar();
}
return *this;
}
inline IO &operator>>(double &d)
{
if ((*this) >> tmp)
sscanf(tmp, "%lf", &d);
return *this;
}
#define defineInFor(intType) \
inline IO &operator>>(intType &n) \
{ \
if (skipBlanks()) \
{ \
int sign = +1; \
if (peekChar() == '-') \
{ \
sign = -1; \
n = nextChar() - '0'; \
} \
else \
n = peekChar() - '0'; \
while (!isBlank(nextChar())) \
{ \
n += n + (n << 3) + peekChar() - 48; \
} \
n *= sign; \
} \
return *this; \
}
defineInFor(int)
defineInFor(unsigned int)
defineInFor(long long)
// fast output routines
//#define putChar(c) putc_unlocked((c), stdout)
inline void putChar(char c)
{
putc_unlocked(c, stdout);
}
inline IO &operator<<(char c)
{
putChar(c);
return *this;
}
inline IO &operator<<(const char *s)
{
while (*s)
putChar(*s++);
return *this;
}
inline IO &operator<<(const string &s)
{
for (int i = 0; i < (int)s.size(); ++i)
putChar(s[i]);
return *this;
}
char *toString(double d)
{
sprintf(tmp, "%lf%c", d, '\0');
return tmp;
}
inline IO &operator<<(double d) { return (*this) << toString(d); }
#define defineOutFor(intType) \
inline char *toString(intType n) \
{ \
char *p = (tmp + 30); \
if (n) \
{ \
bool isNeg = 0; \
if (n < 0) \
isNeg = 1, n = -n; \
while (n) \
*--p = (n % 10) + '0', n /= 10; \
if (isNeg) \
*--p = '-'; \
} \
else \
*--p = '0'; \
return p; \
} \
inline IO &operator<<(intType n) { return (*this) << toString(n); }
defineOutFor(int)
defineOutFor(long long)
#define endl ('\n')
#define cout __io__
#define cin __io__
} __io__;
int main()
{
ll Q;
cin >> Q;
loop(i, Q)
{
ll X;
cin >> X;
if (MR(X))
cout << X << " " << 1 << '\n';
else
cout << X << " " << 0 << '\n';
}
return 0;
}