#210191 (D) No.577 Prime Powerful Numbers

提出ソース
結果

問題	No.577 Prime Powerful Numbers
ユーザー	yosupot
提出日時	2017-10-16 13:04:00
言語	D (dmd 2.106.1)
結果	AC
実行時間	416 ms / 2,000 ms
コード長	16,986 bytes
コンパイル時間	946 ms
コンパイル使用メモリ	104,876 KB
実行使用メモリ	6,944 KB
最終ジャッジ日時	2024-06-12 22:03:09
合計ジャッジ時間	2,296 ms
ジャッジサーバーID （参考情報）	judge1 / judge4
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	6 ms 6,812 KB
testcase_01	AC	20 ms 6,944 KB
testcase_02	AC	3 ms 6,940 KB
testcase_03	AC	80 ms 6,940 KB
testcase_04	AC	13 ms 6,940 KB
testcase_05	AC	396 ms 6,940 KB
testcase_06	AC	29 ms 6,940 KB
testcase_07	AC	416 ms 6,940 KB
testcase_08	AC	77 ms 6,944 KB
testcase_09	AC	69 ms 6,940 KB
testcase_10	AC	1 ms 6,940 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
/+ 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;
        static if (N == 2) {
            auto u = mul128(d[0], r[0]);
            res[0] = u[0];
            res[1] = u[1] + d[0]*r[1] + d[1]*r[0];
            return res;
        } else {
            foreach (i; 0..N) {
                ulong carry = 0;
                foreach (j; 0..N-1-i) {
                    int s = i+j;
                    bool of;
                    auto u = mul128(d[i], r[j]);
                    res[s] = addu(res[s], carry, of);
                    carry = u[1];
                    if (of) carry++;
                    res[s] = addu(res[s], u[0], of);
                    if (of) carry++;
                }
                res[N-1] += d[i] * r[N-1-i] + carry;
            }
            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 {
        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);
    }
    ulong opBinary(string op : "%")(ulong r) const if (N == 2) {
        ulong z = d[1] % r;
        return d[0] - div128([d[0], z], r) * r;
    }
    uintN opBinary(string op : "%")(in uintN r) const {
        static if (N == 2) {
            if (r[1] == 0) return uintN(this % ulong(r[0]));
        }
        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)
*/
yukicoder

結果

テストケース

ソースコード
