結果
| 問題 |
No.577 Prime Powerful Numbers
|
| コンテスト | |
| ユーザー |
 yosupot
|
| 提出日時 | 2017-10-16 10:04:00 |
| 言語 | D (dmd 2.109.1) |
| 結果 |
AC
|
| 実行時間 | 834 ms / 2,000 ms |
| コード長 | 16,571 bytes |
| コンパイル時間 | 678 ms |
| コンパイル使用メモリ | 104,588 KB |
| 実行使用メモリ | 6,944 KB |
| 最終ジャッジ日時 | 2024-06-12 22:01:51 |
| 合計ジャッジ時間 | 3,414 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 10 |
ソースコード
/+ dub.sdl:
name "A"
dependency "dcomp" version=">=0.7.3"
+/
import std.stdio, std.algorithm, std.range, std.conv;
// import dcomp.foundation, dcomp.scanner;
T pow_mod(T)(T x, long n, T md) {
T r = 1;
while (n) {
if (n & 1) r = (r*x)%md;
x = (x*x)%md;
n >>= 1;
}
return r % md;
}
// import dcomp.bigint;
bool isPrime(long n) {
if (n <= 1) return false;
if (n == 2) return true;
if (n % 2 == 0) return false;
alias Int = uintN!2;
long d = n-1;
while (d % 2 == 0) d /= 2;
long[] alist = [2,3,5,7,11,13,17,19,23,29,31,37];
foreach (a; alist) {
if (n <= a) break;
long t = d;
Int y = pow_mod!Int(Int(a), t, Int(n));
while (t != n-1 && y != Int(1) && y != Int(n-1)) {
y = y*y % Int(n);
t <<= 1;
}
if (y != Int(n-1) && t % 2 == 0) {
return false;
}
}
return true;
}
bool ck2(long x) {
import std.math;
if (isPrime(x)) return true;
foreach (i; 2..100) {
long y = cast(long)(pow(x, 1.0/i) + 0.001);
if (!isPrime(y)) continue;
long z = 1;
foreach (j; 0..i) z *= y;
if (z == x) return true;
}
return false;
}
bool solve(long x) {
if (x == 2) return false;
if (x % 2 == 0) return true;
long b = 2;
while (b < x) {
if (ck2(x-b)) return true;
b *= 2;
}
return false;
}
int main() {
Scanner sc = new Scanner(stdin);
// Scanner sc = new Scanner(File("tests/Ain0.txt"));
int q;
sc.read(q);
foreach (i; 0..q) {
long x;
sc.read(x);
if (solve(x)) writeln("Yes");
else writeln("No");
}
return 0;
}
/* IMPORT /Users/yosupo/Program/dcomp/source/dcomp/bigint.d */
// module dcomp.bigint;
import core.checkedint, core.bitop;
// import dcomp.int128, dcomp.foundation;
void addMultiWord(in ulong[] l, in ulong[] r, ulong[] res) {
auto N = res.length;
bool of = false;
foreach (i; 0..N) {
bool nof;
res[i] = addu(
(i < l.length) ? l[i] : 0UL,
(i < r.length) ? r[i] : 0UL, nof);
if (of) {
res[i]++;
nof |= (res[i] == 0);
}
of = nof;
}
}
void subMultiWord(in ulong[] l, in ulong[] r, ulong[] res) {
auto N = res.length;
bool of = false;
foreach (i; 0..N) {
bool nof;
res[i] = subu(
(i < l.length) ? l[i] : 0UL,
(i < r.length) ? r[i] : 0UL, nof);
if (of) {
res[i]--;
nof |= (res[i] == ulong.max);
}
of = nof;
}
}
void mulMultiWord(in ulong[] l, in ulong r, ulong[] res) {
auto N = res.length;
ulong ca;
foreach (i; 0..N) {
auto u = mul128((i < l.length) ? l[i] : 0UL, r);
bool of;
res[i] = addu(u[0], ca, of);
if (of) u[1]++;
ca = u[1];
}
}
void shiftLeftMultiWord(in ulong[] l, int n, ulong[] res) {
size_t N = res.length;
int ws = n / 64;
int bs = n % 64;
import std.stdio;
foreach_reverse (ptrdiff_t i; 0..N) {
ulong b = (0 <= i-ws && i-ws < l.length) ? l[i-ws] : 0UL;
if (bs == 0) res[i] = b;
else {
ulong a = (0 <= i-ws-1 && i-ws-1 < l.length) ? l[i-ws-1] : 0UL;
res[i] = (b << bs) | (a >> (64-bs));
}
}
}
int cmpMultiWord(in ulong[] l, in ulong[] r) {
import std.algorithm : max;
auto N = max(l.length, r.length);
foreach_reverse (i; 0..N) {
auto ld = (i < l.length) ? l[i] : 0UL;
auto rd = (i < r.length) ? r[i] : 0UL;
if (ld < rd) return -1;
if (ld > rd) return 1;
}
return 0;
}
struct uintN(int N) if (N >= 1) {
import core.checkedint;
ulong[N] d;
this(ulong x) { d[0] = x; }
this(string s) {
foreach (c; s) {
this *= 10;
this += uintN(c-'0');
}
}
string toString() {
import std.algorithm : reverse;
char[] s;
if (!this) return "0";
while (this) {
s ~= cast(char)('0' + (this % uintN(10))[0]);
this /= uintN(10);
}
reverse(s);
return s.idup;
}
ref inout(ulong) opIndex(int idx) inout { return d[idx]; }
T opCast(T: bool)() {
import std.algorithm, std.range;
return d[].find!"a!=0".empty == false;
}
uintN opUnary(string op)() const if (op == "~") {
uintN res;
foreach (i; 0..N) {
res[i] = ~d[i];
}
return res;
}
uintN opBinary(string op)(in uintN r) const
if (op == "&" || op == "|" || op == "^") {
uintN res;
foreach (i; 0..N) {
res[i] = mixin("d[i]" ~ op ~ "r.d[i]");
}
return res;
}
uintN opBinary(string op : "<<")(int n) const {
if (N * 64 <= n) return uintN(0);
uintN res;
int ws = n / 64;
int bs = n % 64;
if (bs == 0) {
res.d[ws..N][] = d[0..N-ws][];
return res;
}
foreach_reverse (i; 1..N-ws) {
res[i+ws] = (d[i] << bs) | (d[i-1] >> (64-bs));
}
res[ws] = (d[0] << bs);
return res;
}
uintN opBinary(string op : ">>")(int n) const {
if (N * 64 <= n) return uintN(0);
uintN res;
int ws = n / 64;
int bs = n % 64;
if (bs == 0) {
res.d[0..N-ws][] = d[ws..N][];
return res;
}
foreach_reverse (i; 0..N-ws-1) {
res[i] = (d[i+ws+1] >> (64-bs)) | (d[i+ws] << bs);
}
res[N-ws-1] = (d[N-1] << bs);
return res;
}
int opCmp(in uintN r) const {
return cmpMultiWord(d, r.d);
}
uintN opUnary(string op)() if (op == "++") {
uintN res;
bool of = true;
foreach (i; 0..N) {
if (of) {
d[i]++;
if (d[i]) of = false;
}
}
return res;
}
uintN opUnary(string op)() if (op == "--") {
return this -= uintN(1);
}
uintN opUnary(string op)() const if (op=="+" || op=="-") {
if (op == "+") return this;
if (op == "-") {
return ++(~this);
}
}
uintN opBinary(string op : "+")(in uintN r) const {
uintN res;
addMultiWord(d, r.d, res.d);
return res;
}
uintN opBinary(string op : "-")(in uintN r) const {
uintN res;
subMultiWord(d, r.d, res.d);
return res;
}
uintN opBinary(string op : "*")(in uintN r) const {
uintN res;
foreach (s; 0..N) {
foreach (i; 0..s+1) {
int j = s-i;
auto u = mul128(d[i], r[j]);
bool of;
res[s] = addu(res[s], u[0], of);
if (s+1 < N) {
if (of) {
res[s+1]++;
of = (res[s+1] == 0);
}
res[s+1] = addu(res[s+1], u[1], of);
if (s+2 < N && of) res[s+2]++;
}
}
}
return res;
}
uintN opBinary(string op : "*")(in ulong r) const {
uintN res;
mulMultiWord(d, r, res.d);
return res;
}
uintN opBinary(string op : "/")(ulong rr) const {
import std.stdio;
uintN res;
ulong back = 0;
foreach_reverse (i; 0..N) {
assert(back < rr);
ulong pred = div128([d[i], back], rr);
res[i] = pred;
back = d[i]-(rr*pred);
}
return res;
}
uintN opBinary(string op : "/")(in uintN rr) const {
int up = -1, shift;
foreach_reverse (i; 0..N) {
if (rr[i]) {
up = i;
shift = 63 - bsr(rr[i]);
break;
}
}
assert(up != -1);
if (up == 0) {
return this / ulong(rr[0]);
}
ulong[N+1] l;
l[0..N] = d[0..N];
shiftLeftMultiWord(l, shift, l);
auto r = (rr << shift);
uintN res;
foreach_reverse (i; 0..N-up) {
ulong pred = (r[up] == ulong.max) ? l[i+up+1] : div128([l[i+up], l[i+up+1]], r[up]+1);
res[i] = pred;
ulong[N+1] buf;
mulMultiWord(r.d[], pred, buf);
subMultiWord(l[i..i+up+2], buf[], l[i..i+up+2]);
while (cmpMultiWord(l[i..i+up+2], r.d[]) != -1) {
res[i]++;
subMultiWord(l[i..i+up+2], r.d[], l[i..i+up+2]);
}
}
return res;
}
uintN opBinary(string op : "/")(in ulong r) const {
return this / uintN(r);
}
uintN opBinary(string op : "%", T)(in T r) const {
return this - this/r*r;
}
auto opOpAssign(string op, T)(in T r) {
return mixin("this=this" ~ op ~ "r");
}
}
/* IMPORT /Users/yosupo/Program/dcomp/source/dcomp/array.d */
// module dcomp.array;
T[N] fixed(T, size_t N)(T[N] a) {return a;}
struct FastAppender(A, size_t MIN = 4) {
import std.algorithm : max;
import std.conv;
import std.range.primitives : ElementEncodingType;
import core.stdc.string : memcpy;
private alias T = ElementEncodingType!A;
private T* _data;
private uint len, cap;
@property size_t length() const {return len;}
bool empty() const { return len == 0; }
void reserve(size_t nlen) {
import core.memory : GC;
if (nlen <= cap) return;
void* nx = GC.malloc(nlen * T.sizeof);
cap = nlen.to!uint;
if (len) memcpy(nx, _data, len * T.sizeof);
_data = cast(T*)(nx);
}
void free() {
import core.memory : GC;
GC.free(_data);
}
void opOpAssign(string op : "~")(T item) {
if (len == cap) {
reserve(max(MIN, cap*2));
}
_data[len++] = item;
}
void insertBack(T item) {
this ~= item;
}
void removeBack() {
len--;
}
void clear() {
len = 0;
}
ref inout(T) back() inout { assert(len); return _data[len-1]; }
ref inout(T) opIndex(size_t i) inout { return _data[i]; }
T[] data() {
return (_data) ? _data[0..len] : null;
}
}
/* IMPORT /Users/yosupo/Program/dcomp/source/dcomp/scanner.d */
// module dcomp.scanner;
// import dcomp.array;
class Scanner {
import std.stdio : File;
import std.conv : to;
import std.range : front, popFront, array, ElementType;
import std.array : split;
import std.traits : isSomeChar, isStaticArray, isArray;
import std.algorithm : map;
File f;
this(File f) {
this.f = f;
}
char[512] lineBuf;
char[] line;
private bool succW() {
import std.range.primitives : empty, front, popFront;
import std.ascii : isWhite;
while (!line.empty && line.front.isWhite) {
line.popFront;
}
return !line.empty;
}
private bool succ() {
import std.range.primitives : empty, front, popFront;
import std.ascii : isWhite;
while (true) {
while (!line.empty && line.front.isWhite) {
line.popFront;
}
if (!line.empty) break;
line = lineBuf[];
f.readln(line);
if (!line.length) return false;
}
return true;
}
private bool readSingle(T)(ref T x) {
import std.algorithm : findSplitBefore;
import std.string : strip;
import std.conv : parse;
if (!succ()) return false;
static if (isArray!T) {
alias E = ElementType!T;
static if (isSomeChar!E) {
auto r = line.findSplitBefore(" ");
x = r[0].strip.dup;
line = r[1];
} else static if (isStaticArray!T) {
foreach (i; 0..T.length) {
bool f = succW();
assert(f);
x[i] = line.parse!E;
}
} else {
FastAppender!(E[]) buf;
while (succW()) {
buf ~= line.parse!E;
}
x = buf.data;
}
} else {
x = line.parse!T;
}
return true;
}
int read(T, Args...)(ref T x, auto ref Args args) {
if (!readSingle(x)) return 0;
static if (args.length == 0) {
return 1;
} else {
return 1 + read(args);
}
}
}
/* IMPORT /Users/yosupo/Program/dcomp/source/dcomp/foundation.d */
// module dcomp.foundation;
static if (__VERSION__ <= 2070) {
/*
Copied by https://github.com/dlang/phobos/blob/master/std/algorithm/iteration.d
Copyright: Andrei Alexandrescu 2008-.
License: $(HTTP boost.org/LICENSE_1_0.txt, Boost License 1.0).
*/
template fold(fun...) if (fun.length >= 1) {
auto fold(R, S...)(R r, S seed) {
import std.algorithm : reduce;
static if (S.length < 2) {
return reduce!fun(seed, r);
} else {
import std.typecons : tuple;
return reduce!fun(tuple(seed), r);
}
}
}
}
version (X86) static if (__VERSION__ < 2071) {
import core.bitop : bsf, bsr, popcnt;
int bsf(ulong v) {
foreach (i; 0..64) {
if (v & (1UL << i)) return i;
}
return -1;
}
int bsr(ulong v) {
foreach_reverse (i; 0..64) {
if (v & (1UL << i)) return i;
}
return -1;
}
int popcnt(ulong v) {
int c = 0;
foreach (i; 0..64) {
if (v & (1UL << i)) c++;
}
return c;
}
}
/* IMPORT /Users/yosupo/Program/dcomp/source/dcomp/ldc/inline.d */
// module dcomp.ldc.inline;
version(LDC) {
pragma(LDC_inline_ir)
R inlineIR(string s, R, P...)(P);
}
/* IMPORT /Users/yosupo/Program/dcomp/source/dcomp/int128.d */
// module dcomp.int128;
// import dcomp.array;
version(LDC) {
// import dcomp.ldc.inline;
}
version(LDC) version(X86_64) {
version = LDC_IR;
}
ulong[2] mul128(ulong a, ulong b) {
ulong[2] res;
version(LDC_IR) {
ulong upper, lower;
inlineIR!(`
%r0 = zext i64 %0 to i128
%r1 = zext i64 %1 to i128
%r2 = mul i128 %r1, %r0
%r3 = trunc i128 %r2 to i64
%r4 = lshr i128 %r2, 64
%r5 = trunc i128 %r4 to i64
store i64 %r3, i64* %2
store i64 %r5, i64* %3`, void)(a, b, &lower, &upper);
return [lower, upper];
} else version(D_InlineAsm_X86_64) {
ulong upper, lower;
asm {
mov RAX, a;
mul b;
mov lower, RAX;
mov upper, RDX;
}
return [lower, upper];
} else {
ulong B = 2UL^^32;
ulong[2] a2 = [a % B, a / B];
ulong[2] b2 = [b % B, b / B];
ulong[4] c;
foreach (i; 0..2) {
foreach (j; 0..2) {
c[i+j] += a2[i] * b2[j] % B;
c[i+j+1] += a2[i] * b2[j] / B;
}
}
foreach (i; 0..3) {
c[i+1] += c[i] / B;
c[i] %= B;
}
return [c[0] + c[1] * B, c[2] + c[3] * B];
}
}
ulong div128(ulong[2] a, ulong b) {
version(LDC_IR) {
return inlineIR!(`
%r0 = zext i64 %0 to i128
%r1 = zext i64 %1 to i128
%r2 = shl i128 %r1, 64
%r3 = add i128 %r0, %r2
%r4 = zext i64 %2 to i128
%r5 = udiv i128 %r3, %r4
%r6 = trunc i128 %r5 to i64
ret i64 %r6`,ulong)(a[0], a[1], b);
} else version(D_InlineAsm_X86_64) {
ulong upper = a[1], lower = a[0];
ulong res;
asm {
mov RDX, upper;
mov RAX, lower;
div b;
mov res, RAX;
}
return res;
} else {
import std.bigint, std.conv;
return (((BigInt(a[1]) << 64) + BigInt(a[0])) / BigInt(b)).to!string.to!ulong;
}
}
/*
This source code generated by dcomp and include dcomp's source code.
dcomp's Copyright: Copyright (c) 2016- Kohei Morita. (https://github.com/yosupo06/dcomp)
dcomp's License: MIT License(https://github.com/yosupo06/dcomp/blob/master/LICENSE.txt)
*/