結果
| 問題 |
No.8030 ミラー・ラビン素数判定法のテスト
|
| ユーザー |
 tetora1011
|
| 提出日時 | 2021-05-08 19:32:45 |
| 言語 | C# (.NET 8.0.404) |
| 結果 |
AC
|
| 実行時間 | 7,182 ms / 9,973 ms |
| コード長 | 18,740 bytes |
| コンパイル時間 | 11,355 ms |
| コンパイル使用メモリ | 167,280 KB |
| 実行使用メモリ | 198,376 KB |
| 最終ジャッジ日時 | 2024-11-16 23:39:24 |
| 合計ジャッジ時間 | 33,968 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 10 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (102 ms)。 MSBuild のバージョン 17.9.6+a4ecab324 (.NET) main -> /home/judge/data/code/bin/Release/net8.0/main.dll main -> /home/judge/data/code/bin/Release/net8.0/publish/
ソースコード
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Text;
namespace No3030
{
class Program
{
public static void Solve(Input input)
{
var n = input.NextInt();
var xx = input.NextLong(n);
foreach (var x in xx)
{
Console.WriteLine($"{x} {(MathEx.IsPrime(x) ? 1 : 0)}");
}
}
/// <summary>
/// 最大公約数
/// 最小公倍数
/// 拡張ユークリッド互除法
///
/// 約数列挙
///
/// 素数判定
/// 素数の個数
/// 素因数分解
/// 素数列挙（エラトステネスの篩）
/// </summary>
public static class MathEx
{
#region GCD / LCM
/// <summary>
/// 最大公約数
/// ユークリッド互除法
/// </summary>
public static long Gcd(long a, long b)
{
long r;
while ((r = a % b) != 0)
{
a = b;
b = r;
}
return b;
}
/// <summary>
/// 最大公約数
/// </summary>
public static long Gcd(IEnumerable<long> nums)
=> nums.Aggregate((n, next) => n = Gcd(n, next));
/// <summary>
/// 最大公約数
/// </summary>
public static int Gcd(IEnumerable<int> nums)
=> (int)Gcd(nums.Select(x => (long)x));
/// <summary>
/// 最小公倍数
/// </summary>
public static long Lcm(long a, long b)
=> a / Gcd(a, b) * b;
/// <summary>
/// 最小公倍数
/// </summary>
public static long Lcm(IEnumerable<long> nums)
=> nums.Aggregate((n, next) => n = Lcm(n, next));
/// <summary>
/// 最小公倍数
/// </summary>
public static long Lcm(IEnumerable<int> nums)
=> Lcm(nums.Select(x => (long)x));
/// <summary>
/// 拡張ユークリッドの互除法
/// ax+by = gcd(a,b)の整数解
/// </summary>
public static void ExtendedGcd(long a, long b, out long x, out long y)
{
long u = 0, v = 1;
x = 1; y = 0;
while (b > 0)
{
long q = a / b;
long t;
t = u;
u = x - q * u;
x = t;
t = v;
v = y - q * v;
y = t;
t = b;
b = a - q * b;
a = t;
}
}
#endregion
#region 約数列挙
/// <summary>
/// 約数列挙 順番はバラバラなので注意！
/// </summary>
private static IEnumerable<long> Divisors(long n)
{
if (n < 1) yield break;
var rn = (int)(Math.Sqrt(n) + 1);
for (long i = 1; i < rn; i++)
{
if ((n % i) == 0)
{
yield return i;
if (i != (n / i)) yield return n / i;
}
}
}
/// <summary>
/// 約数列挙
/// </summary>
/// <param name="n"></param>
/// <param name="needsSort">昇順ソートするか</param>
/// <returns></returns>
public static long[] Divisors(long n, bool needsSort = false)
{
var divs = Divisors(n).ToArray();
if (needsSort) Array.Sort(divs);
return divs;
}
#endregion
#region 素数
/// <summary>
/// 素数判定
/// </summary>
public static bool IsPrime(ulong n)
{
// 小さい数の時は試し割が早い気がするので分岐しておく
// ただししきい値は適当……
if (n < 100)
{
return IsPrimeTrialDiv(n);
}
else
{
return IsPrimeMillerRabin(n);
}
}
/// <summary>
/// 素数判定(試し割)
/// </summary>
private static bool IsPrimeTrialDiv(ulong n)
{
if (n <= 2) return n == 2;
if ((n % 2) == 0) return false;
ulong rn = (ulong)(Math.Sqrt(n) + 1);
for (ulong m = 3; m < rn; m += 2)
{
if ((n % m) == 0)
{
return false;
}
}
return true;
}
private static readonly int[] _millerRabinWitness32 = new int[] { 2, 7, 61 };
private static readonly int[] _millerRabinWitness64 = new int[] { 2, 325, 9375, 28178, 450775, 9780504, 1795265022 };
/// <summary>
/// 素数判定
/// </summary>
/// <param name="n"></param>
/// <returns></returns>
/// <remarks>
/// ミラー・ラビンによる
/// 本来は確率的アルゴリズムだが任意の範囲においては
/// 対応する数列すべてにクリアすれば素数と見なせる
/// 2^32 <=> {2, 7, 61}
/// 2^64 <=> {2, 325, 9375, 28178, 450775, 9780504, 1795265022}
///
/// 内部処理の関係上、本当に2^64とか極端に大きな数は計算できないことに注意
/// </remarks>
private static bool IsPrimeMillerRabin(ulong n)
{
if (n >= 1ul << 63)
{
throw new ArgumentOutOfRangeException(nameof(n));
}
if (n <= 2) return n == 2;
if ((n % 2) == 0) return false;
ulong n1 = n - 1;
ulong d = n1 / 2;
while ((d & 1) == 0)
{
d /= 2;
}
var witness = ((n >> 32) != 0) ? _millerRabinWitness64 : _millerRabinWitness32;
foreach (ulong m in witness)
{
if (m % n == 0) { continue; }
var t = d;
var r = ModPower(m, t, n);
while (t != n1 && r != 1 && r != n1)
{
r = ModPower(r, 2, n);
t *= 2;
}
if (r != n1 && (t & 1) == 0) { return false; }
}
return true;
}
/// <summary>
/// n以下の素数判定リスト
/// </summary>
public static bool[] Sieve(int n)
{
// Sieve of Eratosthenes
var sieve = Enumerable.Repeat(true, n + 1).ToArray();
if (n > 2)
{
sieve[0] = sieve[1] = false;
}
var rn = (int)(Math.Sqrt(n) + 1);
foreach (var i in Enumerable.Range(2, rn - 2))
{
if (sieve[i])
{
for (int j = 2 * i; j <= n; j += i)
{
sieve[j] = false;
}
}
}
return sieve;
}
/// <summary>
/// n以下の素数リスト
/// </summary>
public static IEnumerable<int> GetPrimeList(int n)
{
var sieve = Sieve(n);
return sieve.Select((x, i) => new { X = x, I = i })
.Where(x => x.X)
.Select(x => x.I);
}
/// <summary>
/// n以下の素数の個数
/// </summary>
/// <param name="n"></param>
/// <returns></returns>
/// <remarks>
/// http://hidnoblog.blog46.fc2.com/?m&no=1449
/// </remarks>
public static long CountPrime(long n)
{
int rn = (int)Math.Sqrt(n);
var pp = GetPrimeList(rn + 1).ToArray();
long len = rn + n / (rn + 1) + 1;
var dp = new long[len + 1];
for (int i = 1; i <= rn; i++)
{
dp[i] = n / i - 1;
}
for (int i = rn + 1; i < len; i++)
{
dp[i] = len - i - 1;
}
for (int i = 0; i < pp.Length; i++)
{
for (int j = 1; j < len; j++)
{
var t = (j <= rn ? n / j : (len - j)) / pp[i];
if (t < pp[i]) { break; }
dp[j] -= dp[t > rn ? n / t : len - t] - dp[len - (pp[i] - 1)];
}
}
// dp[i]: n以下の素数をiで除した数
return dp[1];
}
/// <summary>
/// 素因数分解
/// 素数(Key)がValue個ある
/// </summary>
public static Dictionary<long, int> Factorization(long n)
{
var map = new Dictionary<long, int>();
for (long p = 2; p * p <= n; p++)
{
int count = 0;
while (n % p == 0)
{
count++;
n /= p;
}
if (count != 0) map.Add(p, count);
}
if (n > 1) map.Add(n, 1);
return map;
}
/// <summary>
/// 素因数分解
/// 素数をならした配列
/// </summary>
public static long[] FactorizationFlat(long n)
=> Factorization(n)
.SelectMany(x => Enumerable.Repeat(x.Key, x.Value))
.ToArray();
/// <summary>
/// nと互いに素でn以下である自然数の個数
/// オイラーのファイ関数
/// </summary>
public static long CoprimeCount(long n)
{
var primes = Factorization(n);
return primes.Aggregate(n, (t, u) => t - t / u.Key);
}
/// <summary>
/// ルジャンドルの公式
/// n!をpで何回割り切れるか(pは素数)
/// </summary>
public static long Legendres(long n, long p)
{
long count = 0;
for (long m = p; m < n; m *= p)
{
count += n / m;
}
return count;
}
#endregion
#region Misc
/// <summary>
/// Mを法とする乗算
/// </summary>
private static ulong ModMul(ulong a, ulong b, ulong M)
{
a %= M;
b %= M;
ulong r = 0;
if (a < ulong.MaxValue / b)
{
r = (a * b) % M;
}
else
{
// オーバーフローしそうなので地道に行なう
while (b != 0)
{
if ((b & 1) != 0) { r = (r + a) % M; }
a = (a + a) % M;
b >>= 1;
}
return r;
}
return r;
}
/// <summary>
/// Mを法とする累乗
/// </summary>
private static ulong ModPower(ulong a, ulong b, ulong M)
{
ulong r = 1;
while (b > 0)
{
if ((b & 1) != 0) r = ModMul(r, a, M);
a = ModMul(a, a, M);
b >>= 1;
}
return r;
}
#endregion
}
#region Main
public static void Main(string[] args)
{
// 出力が少ないときはこれをセットする方が時間かかるけれど
// そのときにTLEするのはアルゴリズムが悪いせいだし、まあ良しとする
var needsFlushOutput = true;
if (needsFlushOutput)
{
// 細かく出力しないようにする
var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
Console.SetOut(sw);
}
// 通常は引数無しで、ファイルから読み出したい場合はpath指定する
var input = new Input();
// 仮想的に標準入力をセットする
// テスト入力したまま提出することがままあるので……
#if DEBUG
input.SetText("");
#endif
Solve(input);
Console.Out.Flush();
}
#endregion
#region Competitive Template
#pragma warning disable CS0414
static readonly int MOD = (int)1e9 + 7;
static readonly int[] dx = { 1, 0, -1, 0 };
static readonly int[] dy = { 0, 1, 0, -1 };
/// <summary> 左上が原点 </summary>
static readonly char[] dir = { 'R', 'U', 'L', 'D' };
#pragma warning restore CS0414
public class Input
{
// 変な改行コードがたまに混じっているので、一応セパレート指定する
// スペース単独指定の方がもちろん早い
static readonly char[] separator = { ' ', '\r', '\n' };
readonly StreamReader sr;
readonly Queue<string> queue;
/// <summary>
/// 特定のファイルから読み出したい場合はpath指定する
/// </summary>
public Input(string path = "")
{
queue = new Queue<string>();
if (string.IsNullOrEmpty(path)) { sr = new StreamReader(Console.OpenStandardInput()); }
else { sr = new StreamReader(path); }
}
/// <summary>
/// 入力予約
/// </summary>
public void SetText(IEnumerable<string> items)
{
foreach (var item in items)
SetText(item);
}
/// <summary>
/// 入力予約
/// </summary>
public bool SetText(string s)
{
if (string.IsNullOrEmpty(s)) return false;
foreach (var elem in s.Trim().Split(separator, StringSplitOptions.RemoveEmptyEntries))
queue.Enqueue(elem);
return true;
}
/// <summary>
/// 要素が存在するか
/// </summary>
public bool Any() => queue.Any() || Read();
/// <summary>
/// 内部queueに入力からの値をsplitして格納する
/// </summary>
bool Read()
{
if (!SetText(sr.ReadLine())) return false;
if (!queue.Any()) return Read();
return queue.Any();
}
/// <summary>
/// 次のstringを一つ読み込む
/// </summary>
public string Next()
{
if (!queue.Any() && !Read()) return "";
return queue.Dequeue();
}
/// <summary>
/// 指定個数queueにたまるまでenqueueし続ける
/// </summary>
bool Accumulate(int n)
{
while (queue.Count() < n)
if (!Read()) return false;
return true;
}
public int NextInt() => int.Parse(Next());
public long NextLong() => long.Parse(Next());
public double NextDouble() => double.Parse(Next());
/// <summary>
/// n個の要素をparseして、それぞれにoffsetをaddした配列を返す
/// </summary>
T[] NextT<T>(int n, T offset, Func<string, T> parse, Func<T, T, T> add)
{
if (!Accumulate(n)) return null;
var a = new T[n];
for (int i = 0; i < n; i++)
a[i] = add(parse(queue.Dequeue()), offset);
return a;
}
public string[] Next(int n) => NextT(n, "", x => x, (x, y) => x);
public int[] NextInt(int n, int offset = 0) => NextT(n, offset, int.Parse, (x, y) => x + y);
public ulong[] NextLong(int n, ulong offset = 0) => NextT(n, offset, ulong.Parse, (x, y) => x + y);
public double[] NextDouble(int n, double offset = 0.0) => NextT(n, offset, double.Parse, (x, y) => x + y);
}
static class Utils
{
public static T Max<T>(params T[] objs) => objs.Max();
public static T Min<T>(params T[] objs) => objs.Min();
/// <summary>
/// vでfillされたT[d1][d2]配列を作成する
/// </summary>
public static T[][] Create2DArray<T>(int d1, int d2, T v)
{
return
Enumerable.Repeat(0, d1).Select(_ =>
Enumerable.Repeat(v, d2).ToArray()).ToArray();
}
/// <summary>
/// vでfillされたT[d1][d2][d3]配列を作成する
/// </summary>
public static T[][][] Create3DArray<T>(int d1, int d2, int d3, T v)
{
return
Enumerable.Repeat(0, d1).Select(_ =>
Enumerable.Repeat(0, d2).Select(__ =>
Enumerable.Repeat(v, d3).ToArray()).ToArray()).ToArray();
}
}
#endregion
}
}