結果
| 問題 |
No.8030 ミラー・ラビン素数判定法のテスト
|
| ユーザー |
 iwkjosec
|
| 提出日時 | 2019-05-18 21:58:20 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
WA
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 23,550 bytes |
| コンパイル時間 | 1,050 ms |
| コンパイル使用メモリ | 117,836 KB |
| 実行使用メモリ | 25,896 KB |
| 最終ジャッジ日時 | 2024-11-18 16:42:03 |
| 合計ジャッジ時間 | 4,048 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 9 WA * 1 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Math;
using System.Numerics;
class Program
{
static void Main()
{
var n = long.Parse(ReadLine());
for (int i = 0; i < n; i++)
{
var x = long.Parse(ReadLine());
WriteLine(x.ToString() + " " + (MillerRabin(x) ? "1" : "0"));
}
}
static uint[] l = new uint[] { 2, 325, 9375, 28178, 450775, 9780504, 1795265022 };
static bool MillerRabin(long n)
{
if (n < 2) return false;
if (n % 2 == 0) return n == 2;
var d = n - 1;
var s = 0;
while (d % 2 == 0)
{
s++;
d >>= 1;
}
var dd = (UInt128)d;
var nn = (UInt128)n;
for (int i = 0; i < l.Length && l[i] < n; i++)
{
var a = l[i];
var c = true;
var x = UInt128.ModPow(a, dd, nn);
if (x == 1) c = false;
for (int r = 0; r < s; r++)
{
if (x == nn - 1) c = false;
x = x * x % nn;
}
if (c) return false;
}
return true;
}
}
public struct UInt128
{
public ulong low;
public ulong high;
public UInt128(ulong h, ulong l)
{
low = l;
high = h;
}
public static UInt128 operator +(UInt128 l, UInt128 r)//片方にもう片方足して返すのとin引数にして新しいインスタンス返すのどっちがいいんだろう
{
var s = new UInt128 { low = l.low + r.low, high = l.high + r.high };
if (s.low < l.low) s.high++;
return s;
}
public static UInt128 operator -(UInt128 l, UInt128 r)
{
var s = new UInt128 { low = l.low - r.low, high = l.high - r.high };
if (s.low > l.low) s.high--;
return s;
}
public static UInt128 operator *(UInt128 l, UInt128 r)//導出は n bit * n bit -> 2n bit ができないとき 上位ビット下位ビットに分割して考える
{
var h = l.low * r.high + l.high * r.low;
var lll = l.low & 0xFFFFFFFF;
var llh = l.low >> 32;
var rll = r.low & 0xFFFFFFFF;
var rlh = r.low >> 32;
var a = lll * rll;
var b = lll * rlh + llh * rll;
var c = llh * rlh;
if (b < lll * rlh) c += 1UL << 32;
var lo = a + (b << 32);
var hi = c + (b >> 32);
if (lo < a) hi++;
hi += h;
return new UInt128 { low = lo, high = hi };
}
public static UInt128 operator /(UInt128 left, UInt128 right)
{
if (right.high == 0) return left / right.low;
if (left < right) return 0;
return left.Divide(right);
}
public static UInt128 operator /(UInt128 left, ulong right)
{
if (right == (uint)right) return left / (uint)right;
if (left < right) return 0;
if (right.IsPowerOf2()) return left >> right.HighBitPosition();
return left.Divide(right);
}
public static UInt128 operator /(UInt128 left, uint right)
{
if (right == 0) throw new DivideByZeroException();
if (left < right) return 0;
if (left.high == 0) return left.low / right;
return left.Divide(right);
}
private ulong Divide(UInt128 denominator)
{
var remainder = this;
ulong result = 0;
var denHiBit = denominator.high.HighBitPosition();
do
{
var remHiBit = remainder.high.HighBitPosition();
var diff = remHiBit - denHiBit;
if (diff <= 3)
{
// div by subtraction
do
{
result++;
remainder -= denominator;
} while (remainder >= denominator);
return result;
}
ulong resLo;
if (denHiBit >= 18 && diff <= 24)
{
// div by divide high ulongs
resLo = remainder.high /
(denominator.high +
1
); // we don't have to worry about denominator.hi being MaxValue and overflowing, because that case handled above
}
else
{
// div by shifted divide
var denShift = denHiBit + 1;
var den = (denominator >> denShift).low;
if (den > remainder.high)
{
// we already know division quotient will fit in a ulong
den++;
if (den == 0)
{
// handle the rare case where the shifted den + 1 overflows
denShift++;
den = 1UL << 31;
}
resLo = DivUnchecked(remainder.high, remainder.low, den);
resLo >>= denShift;
}
else
{
// ensure division quotient will fit in a ulong
den++; // den + 1 can't overflow, because it's less then remainder.hi
var resHi = remainder.high / den;
var remHi = remainder.high - remainder.high / den * den;
var tempResult = new UInt128(resHi, DivUnchecked(remHi, remainder.low, den));
tempResult >>= denShift;
resLo = tempResult.low;
}
}
result += resLo;
remainder -= denominator * resLo;
} while (remainder >= denominator);
return result;
}
// denominator must be > uint.MaxValue
private UInt128 Divide(ulong denominator)
{
ulong resHi = 0;
var remHi = high;
//ensure we can divide a UInt128 by a ulong, and have the quotient fit in a ulong
if (remHi >= denominator)
{
resHi = remHi / denominator;
remHi -= resHi * denominator;
}
return new UInt128(resHi, DivUnchecked(remHi, low, denominator));
}
// denominator must be > uint.MaxValue and > the high parameter
private static ulong DivUnchecked(ulong high, ulong low, ulong denominator)
{
unchecked
{
ulong hiShLo, denHi, denLo, quotHi, quotLo, mid, shLoMid, shLo, rhat, left, right;
if (denominator >> 63 != 0)
{
mid = high;
shLo = low;
}
else
{
// unwind first few iterations of loop to count leading zero bits but use
// bit fiddle if more than 3 to avoid time consuming count when there are
// many leading zero bits. Doing a quick test of the 4 most significant
// bit positions covers about 94% of possible ulong denominator values.
int s;
if (denominator >> 62 != 0) s = 1;
else if (denominator >> 61 != 0) s = 2;
else if (denominator >> 60 != 0) s = 3;
else s = ((uint)(denominator >> 32)).LeadingZeroBits();
denominator <<= s;
mid = (high << s) | (low >> (64 - s));
shLo = low << s;
}
shLoMid = mid << 32;
hiShLo = shLo >> 32;
shLoMid += hiShLo;
denLo = (uint)denominator;
denHi = denominator >> 32;
quotHi = mid / denHi;
if (quotHi != 0)
{
rhat = mid - mid / denHi * denHi;
right = (rhat << 32) | hiShLo;
left = quotHi * denLo;
while (quotHi != (uint)quotHi || left > right)
{
quotHi--;
rhat += denHi;
if (rhat != (uint)rhat) break;
right = (rhat << 32) | hiShLo;
left -= denLo;
}
shLoMid -= quotHi * denominator;
quotHi <<= 32;
}
quotLo = shLoMid / denHi;
rhat = shLoMid - shLoMid / denHi * denHi;
right = (rhat << 32) | (uint)shLo;
left = quotLo * denLo;
while (quotLo != (uint)quotLo || left > right)
{
quotLo--;
rhat += denHi;
if (rhat != (uint)rhat) break;
right = (rhat << 32) | (uint)shLo;
left -= denLo;
}
return quotHi | quotLo;
}
}
internal UInt128 Divide(uint denominator)
{
var hihi = (uint)(high >> 32);
var reshihi = hihi == 0 ? 0 : hihi / denominator;
var remainder = hihi == 0
? (uint)high
: ((ulong)(hihi - hihi / denominator * denominator) << 32) | (uint)high;
var reshilo = (uint)(remainder / denominator);
var remHi = remainder - reshilo * denominator;
remainder = (remHi << 32) | (uint)(low >> 32);
var reslohi = (uint)(remainder / denominator);
remHi = remainder - reslohi * denominator;
remainder = (remHi << 32) | (uint)low;
var reslolo = (uint)(remainder / denominator);
return new UInt128(((ulong)reshihi << 32) | reshilo, ((ulong)reslohi << 32) | reslolo);
}
public static UInt128 operator %(UInt128 left, UInt128 right)
{
if (right.high == 0) return left % right.low;
if (left < right) return left;
if (right.IsPowerOf2()) return left & (right - 1);
return left.Mod(right);
}
public static ulong operator %(UInt128 left, ulong right)
{
if (right == (uint)right) return left % (uint)right;
if (left < right) return left.low;
if (right.IsPowerOf2()) return left.low & (right - 1);
return left.Mod(right);
}
public static uint operator %(UInt128 left, uint right)
{
if (right == 0) throw new DivideByZeroException();
if (left < right) return (uint)left.low;
if (left.high == 0) return (uint)(left.low % right);
if (right.IsPowerOf2()) return (uint)left.low & (right - 1);
return left.Mod(right);
}
// denominator must be <= this and > ulong.MaxValue
internal UInt128 Mod(UInt128 denominator)
{
var remainder = this;
var denHiBit = denominator.high.HighBitPosition();
do
{
var remHiBit = remainder.high.HighBitPosition();
var diff = remHiBit - denHiBit;
if (diff <= 3)
{
// mod by subtraction
do
{
remainder -= denominator;
} while (remainder >= denominator);
return remainder;
}
ulong resLo, den;
if (denHiBit >= 18 && diff <= 24)
{
// mod by divide high ulongs
resLo = remainder.high /
(denominator.high +
1
); // we don't have to worry about denominator.hi being MaxValue and overflowing, because that case handled above
}
else
{
// mod by shifted divide
var denShift = denHiBit + 1;
den = (denominator >> denShift).low;
if (den > remainder.high)
{
// we already know division quotient will fit in a ulong
den++;
if (den == 0)
{
// handle the rare case where the shifted den + 1 overflows
denShift++;
den = 1UL << 31;
}
resLo = DivUnchecked(remainder.high, remainder.low, den);
resLo >>= denShift;
}
else
{
// ensure division quotient will fit in a ulong
den++; // den + 1 can't overflow, because it's less then remainder.hi
var resHi = remainder.high / den;
var remHi = remainder.high - remainder.high / den * den;
var tempResult = new UInt128(resHi, DivUnchecked(remHi, remainder.low, den));
tempResult >>= denShift;
resLo = tempResult.low;
}
}
remainder -= denominator * resLo;
} while (remainder >= denominator);
return remainder;
}
// denominator must be > uint.MaxValue
internal ulong Mod(ulong denominator)
{
unchecked
{
var high = this.high;
var low = this.low;
//ensure we can divide a UInt128 by a ulong, and have the quotient fit in a ulong
if (high >= denominator) high -= high / denominator * denominator;
if (high == 0) return low - low / denominator * denominator;
ulong hiShLo, denHi, denLo, quotHi, quotLo, mid, shLoMid, shLo, rhat, left, right;
int shift;
if (denominator >> 63 != 0)
{
mid = high;
shLo = low;
shift = 0;
}
else
{
// unwind first few iterations of loop to count leading zero bits but use
// bit fiddle if more than 3 to avoid time consuming count when there are
// many leading zero bits. Doing a quick test of the 4 most significant
// bit positions covers about 94% of possible ulong denominator values.
if (denominator >> 62 != 0) shift = 1;
else if (denominator >> 61 != 0) shift = 2;
else if (denominator >> 60 != 0) shift = 3;
else shift = ((uint)(denominator >> 32)).LeadingZeroBits();
denominator <<= shift;
mid = (high << shift) | (low >> (64 - shift));
shLo = low << shift;
}
shLoMid = mid << 32;
hiShLo = shLo >> 32;
shLoMid += hiShLo;
denLo = (uint)denominator;
denHi = denominator >> 32;
quotHi = mid / denHi;
if (quotHi != 0)
{
rhat = mid - mid / denHi * denHi;
right = (rhat << 32) | hiShLo;
left = quotHi * denLo;
while (quotHi != (uint)quotHi || left > right)
{
quotHi--;
rhat += denHi;
if (rhat != (uint)rhat) break;
right = (rhat << 32) | hiShLo;
left -= denLo;
}
shLoMid -= quotHi * denominator;
}
quotLo = shLoMid / denHi;
rhat = shLoMid - shLoMid / denHi * denHi;
right = (rhat << 32) | (uint)shLo;
left = quotLo * denLo;
while (quotLo != (uint)quotLo || left > right)
{
quotLo--;
rhat += denHi;
if (rhat != (uint)rhat) break;
right = (rhat << 32) | (uint)shLo;
left -= denLo;
}
return ((shLoMid << 32) + ((uint)shLo - quotLo * denominator)) >> shift;
}
}
internal uint Mod(uint denominator)
{
var hihi = (uint)(high >> 32);
var remainder = hihi == 0
? (uint)high
: ((ulong)(hihi - hihi / denominator * denominator) << 32) | (uint)high;
var remHi = (remainder % denominator) << 32;
remainder = remHi | (uint)(low >> 32);
remHi = (remainder % denominator) << 32;
remainder = remHi | (uint)low;
return (uint)(remainder % denominator);
}
public static UInt128 operator &(UInt128 l, UInt128 r)
{
return new UInt128 { low = l.low & r.low, high = l.high & r.high };
}
public static UInt128 operator |(UInt128 l, UInt128 r)
{
return new UInt128 { low = l.low | r.low, high = l.high | r.high };
}
public static UInt128 operator ^(UInt128 l, UInt128 r)
{
return new UInt128 { low = l.low ^ r.low, high = l.high ^ r.high };
}
public static UInt128 operator <<(UInt128 value, int shift)
{
if (shift == 0) return value;
return shift >= 64
? new UInt128(value.low << (shift - 64), 0UL)
: new UInt128((value.high << shift) | (value.low >> (64 - shift)), value.low << shift);
}
public static UInt128 operator >>(UInt128 value, int shift)
{
if (shift == 0) return value;
return shift >= 64
? new UInt128(0UL, value.high >> (shift - 64))
: new UInt128(value.high >> shift, (value.low >> shift) | (value.high << (64 - shift)));
}
public static bool operator ==(UInt128 l, UInt128 r)
{
return l.low == r.low && l.high == r.high;
}
public static bool operator !=(UInt128 l, UInt128 r)
{
return l.low != r.low || l.high != r.high;
}
public static bool operator >(UInt128 l, UInt128 r)
{
if (l.high > r.high) return true;
if (l.high < r.high) return false;
return l.low > r.low;
}
public static bool operator <(UInt128 l, UInt128 r)
{
if (l.high < r.high) return true;
if (l.high > r.high) return false;
return l.low < r.low;
}
public static bool operator >=(UInt128 l, UInt128 r)
{
if (l.high > r.high) return true;
if (l.high == r.high && l.low >= r.low) return true;
return false;
}
public static bool operator <=(UInt128 l, UInt128 r)
{
if (l.high < r.high) return true;
if (l.high == r.high && l.low <= r.low) return true;
return false;
}
public static UInt128 operator ~(UInt128 v)
{
v.low = ~v.low;
v.high = ~v.high;
return v;
}
public static UInt128 operator +(UInt128 v)
{
return v;
}
public static UInt128 operator ++(UInt128 v)
{
return v + 1;
}
public static UInt128 operator --(UInt128 v)
{
return v - 1;
}
public static explicit operator UInt128(sbyte v)
{
return new UInt128 { low = (ulong)v };
}
public static implicit operator UInt128(byte v)
{
return new UInt128 { low = v };
}
public static explicit operator UInt128(short v)
{
return new UInt128 { low = (ulong)v };
}
public static implicit operator UInt128(ushort v)
{
return new UInt128 { low = v };
}
public static explicit operator UInt128(int v)
{
return new UInt128 { low = (ulong)v };
}
public static implicit operator UInt128(uint v)
{
return new UInt128 { low = v };
}
public static explicit operator UInt128(long v)
{
return new UInt128 { low = (ulong)v };
}
public static implicit operator UInt128(ulong v)
{
return new UInt128 { low = v };
}
public static explicit operator UInt128(BigInteger v)
{
var ret = new UInt128 { low = (ulong)v };
v >>= 64;
ret.high = (ulong)v;
return ret;
}
public static explicit operator sbyte(UInt128 v)
{
return (sbyte)(v.low & 0x7F);
}
public static explicit operator byte(UInt128 v)
{
return (byte)v.low;
}
public static explicit operator short(UInt128 v)
{
return (short)(v.low & 0x7FFF);
}
public static explicit operator ushort(UInt128 v)
{
return (ushort)v.low;
}
public static explicit operator int(UInt128 v)
{
return (int)v.low & int.MaxValue;
}
public static explicit operator uint(UInt128 v)
{
return (uint)v.low;
}
public static explicit operator long(UInt128 v)
{
return (long)v.low & long.MaxValue;
}
public static explicit operator ulong(UInt128 v)
{
return v.low;
}
public static implicit operator BigInteger(UInt128 v)
{
return (new BigInteger(v.high) << 64) | v.low;
}
public static UInt128 ModPow(UInt128 x, UInt128 n, UInt128 m)
{
var res = (UInt128)1;
while (n != 0)
{
if ((n & 1) == 1) res = res * x % m;
x = x * x % m;
n >>= 1;
}
return res;
}
public static UInt128 Parse(string s)// -0を許容して -nはovfとして扱いたい 要はuint,ulongと挙動をそろえたい
{
if (s is null) throw new ArgumentNullException();
s = s.Trim();
if (s.Length == 0) throw new FormatException();
if (s[0] == '+')
{
if (s.Length == 1) throw new FormatException();
else s = s.Substring(1);
}
var a = -1;
for (int i = 0; i < s.Length; i++)
{
if (s[i] != '0')
{
a = i;
break;
}
}
if (a == -1) return new UInt128 { low = 0, high = 0 };
s = s.Substring(a);
if (s.Length > 39) throw new FormatException();
for (int i = 0; i < s.Length; i++)
{
if ((uint)(s[i] - '0') > '9') throw new FormatException();
}
if (s.Length == 39 && s.CompareTo("340282366920938463463374607431768211456") != 1) throw new OverflowException();
var ret = new UInt128();
for (int i = 0; i < s.Length; i++)
{
ret *= 10;
ret += (uint)(s[i] - '0');
}
return ret;
}
public override string ToString()
{
if (this == 0) return "0";
var a = this;
var ret = new List<char>(40);
while (a != 0)
{
ret.Add((char)((int)(a % 10) + '0'));
a /= 10;
}
ret.Reverse();
return new string(ret.ToArray());
}
public override bool Equals(object obj)
{
return base.Equals(obj);
}
public override int GetHashCode()
{
return base.GetHashCode();
}
}
internal static class SoftWxNumerics
{
private static readonly byte[] DeBruijnLsBsSet =
{
0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
};
public static int HighBitPosition(this uint value)
{
if (value == 0) return -1;
value |= value >> 1;
value |= value >> 2;
value |= value >> 4;
value |= value >> 8;
return DeBruijnLsBsSet[unchecked((value | value >> 16) * 0x07c4acddu) >> 27];
}
public static int HighBitPosition(this ulong value)
{
uint high = (uint)(value >> 32);
return high != 0 ? 32 + HighBitPosition(high) : HighBitPosition((uint)value);
}
public static int LeadingZeroBits(this uint value)
{
return unchecked(31 - HighBitPosition(value));
}
public static bool IsPowerOf2(this uint value)
{
return (value & unchecked(value - 1)) == 0 && value != 0;
}
public static bool IsPowerOf2(this ulong value)
{
return (value & unchecked(value - 1UL)) == 0 && value != 0;
}
public static bool IsPowerOf2(this UInt128 value)
{
return (value & value - 1) == 0 && value != 0;
}
}