結果
| 問題 | No.308 素数は通れません |
| ユーザー |
 紙ぺーぱー
|
| 提出日時 | 2015-12-01 01:56:35 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 8,959 bytes |
| コンパイル時間 | 3,134 ms |
| コンパイル使用メモリ | 112,172 KB |
| 実行使用メモリ | 25,088 KB |
| 最終ジャッジ日時 | 2023-10-12 06:54:01 |
| 合計ジャッジ時間 | 12,135 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge15 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | WA | - |
| testcase_01 | WA | - |
| testcase_02 | WA | - |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | WA | - |
| testcase_14 | WA | - |
| testcase_15 | WA | - |
| testcase_16 | WA | - |
| testcase_17 | WA | - |
| testcase_18 | WA | - |
| testcase_19 | WA | - |
| testcase_20 | WA | - |
| testcase_21 | WA | - |
| testcase_22 | WA | - |
| testcase_23 | WA | - |
| testcase_24 | WA | - |
| testcase_25 | WA | - |
| testcase_26 | WA | - |
| testcase_27 | WA | - |
| testcase_28 | WA | - |
| testcase_29 | WA | - |
| testcase_30 | WA | - |
| testcase_31 | WA | - |
| testcase_32 | WA | - |
| testcase_33 | WA | - |
| testcase_34 | WA | - |
| testcase_35 | WA | - |
| testcase_36 | WA | - |
| testcase_37 | WA | - |
| testcase_38 | WA | - |
| testcase_39 | WA | - |
| testcase_40 | WA | - |
| testcase_41 | WA | - |
| testcase_42 | WA | - |
| testcase_43 | WA | - |
| testcase_44 | WA | - |
| testcase_45 | WA | - |
| testcase_46 | WA | - |
| testcase_47 | WA | - |
| testcase_48 | WA | - |
| testcase_49 | WA | - |
| testcase_50 | WA | - |
| testcase_51 | WA | - |
| testcase_52 | WA | - |
| testcase_53 | WA | - |
| testcase_54 | WA | - |
| testcase_55 | WA | - |
| testcase_56 | WA | - |
| testcase_57 | WA | - |
| testcase_58 | WA | - |
| testcase_59 | WA | - |
| testcase_60 | WA | - |
| testcase_61 | WA | - |
| testcase_62 | WA | - |
| testcase_63 | WA | - |
| testcase_64 | WA | - |
| testcase_65 | WA | - |
| testcase_66 | WA | - |
| testcase_67 | WA | - |
| testcase_68 | WA | - |
| testcase_69 | WA | - |
| testcase_70 | WA | - |
| testcase_71 | WA | - |
| testcase_72 | WA | - |
| testcase_73 | WA | - |
| testcase_74 | WA | - |
| testcase_75 | WA | - |
| testcase_76 | WA | - |
| testcase_77 | WA | - |
| testcase_78 | WA | - |
| testcase_79 | WA | - |
| testcase_80 | WA | - |
| testcase_81 | WA | - |
| testcase_82 | WA | - |
| testcase_83 | WA | - |
| testcase_84 | WA | - |
| testcase_85 | WA | - |
| testcase_86 | WA | - |
| testcase_87 | WA | - |
| testcase_88 | WA | - |
| testcase_89 | WA | - |
| testcase_90 | WA | - |
| testcase_91 | WA | - |
| testcase_92 | WA | - |
| testcase_93 | WA | - |
| testcase_94 | WA | - |
| testcase_95 | WA | - |
| testcase_96 | WA | - |
| testcase_97 | WA | - |
| testcase_98 | WA | - |
| testcase_99 | WA | - |
| testcase_100 | WA | - |
| testcase_101 | WA | - |
| testcase_102 | WA | - |
| testcase_103 | WA | - |
| testcase_104 | WA | - |
| testcase_105 | WA | - |
| testcase_106 | WA | - |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System;
using System.Linq;
using System.Collections.Generic;
using Debug = System.Diagnostics.Debug;
using StringBuilder = System.Text.StringBuilder;
using System.Numerics;
using Point = System.Numerics.Complex;
namespace Program
{
public class Solver
{
bool[] primes = MathEx.Sieve(1000000);
public void Solve()
{
//Write(17, 8);
var s = sc.Scan();
return;
if (s.Length <= 3)
{
var v = int.Parse(s);
for (int i = 3; i < v; i++)
{
var k = (v + i - 1) / i;
var bucket = Enumerate(k, x => new char[i]);
var set = new DisjointSet(v);
for (int j = 0; j < v; j++)
{
bucket[j / i][j % i] = (primes[j + 1]) ? 'x' : 'o';
if (primes[j + 1]) continue;
var u = (j / i - 1);
if (u >= 0 && !primes[j + 1 - i])
set.Unite(j, j - i);
if (j % i > 0 && !primes[j])
set.Unite(j, j - 1);
}
//foreach (var x in bucket) IO.Printer.Out.WriteLine(x.AsString());
if (set.IsUnited(0, v - 1))
{
IO.Printer.Out.WriteLine(i);
return;
}
}
}
else
{
var v = BigInteger.Parse(s) - 8;
if (v % 8 != 1)
{
IO.Printer.Out.WriteLine(8);
}
else
{
long u;
if (long.TryParse(s, out u) && isPrime(u - 8))
{
IO.Printer.Out.WriteLine(14);
}
else IO.Printer.Out.WriteLine(8);
}
}
}
static public long ModPow(long x, long n, long mod)
{
long r = 1;
while (n > 0)
{
if ((n & 1) == 1)
r = r * x % mod;
x = (x * x) % mod;
n >>= 1;
}
return r;
}
bool suspect(long a, long s, long d, long n)
{
var x = ModPow(a, d, n);
if (x == 1) return true;
for (int r = 0; r < s; ++r)
{
if (x == n - 1) return true;
x = x * x % n;
}
return false;
}
// {2,7,61,-1} is for n < 4759123141 (= 2^32)
// {2,3,5,7,11,13,17,19,23,-1} is for n < 10^16 (at least)
bool isPrime(long n)
{
if (n <= 1 || (n > 2 && n % 2 == 0)) return false;
var test = new int[] { 2, 3, 5, 7, 11, 13, 17, 19, 23, -1 };
long d = n - 1, s = 0;
while (d % 2 == 0) { ++s; d /= 2; }
for (int i = 0; test[i] < n && test[i] != -1; ++i)
if (!suspect(test[i], s, d, n)) return false;
return true;
}
public void Write(int v, int i)
{
var k = (v + i - 1) / i;
var bucket = Enumerate(k, x => new char[i]);
var set = new DisjointSet(v);
for (int j = 0; j < v; j++)
{
bucket[j / i][j % i] = (primes[j + 1]) ? 'x' : 'o';
if (primes[j + 1]) continue;
var u = (j / i - 1);
if (u >= 0 && !primes[j + 1 - i])
set.Unite(j, j - i);
if (j % i > 0 && !primes[j])
set.Unite(j, j - 1);
}
IO.Printer.Out.WriteLine("{0} {1}", v, i);
foreach (var x in bucket) IO.Printer.Out.WriteLine(x.AsString());
}
public IO.StreamScanner sc = new IO.StreamScanner(Console.OpenStandardInput());
static T[] Enumerate<T>(int n, Func<int, T> f) { var a = new T[n]; for (int i = 0; i < n; ++i) a[i] = f(i); return a; }
static public void Swap<T>(ref T a, ref T b) { var tmp = a; a = b; b = tmp; }
}
}
#region Ex
namespace Program.IO
{
using System.IO;
using System.Text;
using System.Globalization;
public class Printer : StreamWriter
{
static Printer() { Out = new Printer(Console.OpenStandardOutput()) { AutoFlush = false }; }
public static Printer Out { get; set; }
public override IFormatProvider FormatProvider { get { return CultureInfo.InvariantCulture; } }
public Printer(System.IO.Stream stream) : base(stream, new UTF8Encoding(false, true)) { }
public Printer(System.IO.Stream stream, Encoding encoding) : base(stream, encoding) { }
public void Write<T>(string format, IEnumerable<T> source) { base.Write(format, source.OfType<object>().ToArray()); }
public void WriteLine<T>(string format, IEnumerable<T> source) { base.WriteLine(format, source.OfType<object>().ToArray()); }
}
public class StreamScanner
{
public StreamScanner(Stream stream) { str = stream; }
public readonly Stream str;
private readonly byte[] buf = new byte[1024];
private int len, ptr;
public bool isEof = false;
public bool IsEndOfStream { get { return isEof; } }
private byte read()
{
if (isEof) return 0;
if (ptr >= len) { ptr = 0; if ((len = str.Read(buf, 0, 1024)) <= 0) { isEof = true; return 0; } }
return buf[ptr++];
}
public char Char() { byte b = 0; do b = read(); while ((b < 33 || 126 < b) && !isEof); return (char)b; }
public string Scan()
{
var sb = new StringBuilder();
for (var b = Char(); b >= 33 && b <= 126; b = (char)read())
sb.Append(b);
return sb.ToString();
}
public long Long()
{
if (isEof) return long.MinValue;
long ret = 0; byte b = 0; var ng = false;
do b = read();
while (b != '-' && (b < '0' || '9' < b));
if (b == '-') { ng = true; b = read(); }
for (; true; b = read())
{
if (b < '0' || '9' < b)
return ng ? -ret : ret;
else ret = ret * 10 + b - '0';
}
}
public int Integer() { return (isEof) ? int.MinValue : (int)Long(); }
public double Double() { return double.Parse(Scan(), CultureInfo.InvariantCulture); }
private T[] enumerate<T>(int n, Func<T> f)
{
var a = new T[n];
for (int i = 0; i < n; ++i) a[i] = f();
return a;
}
public char[] Char(int n) { return enumerate(n, Char); }
public string[] Scan(int n) { return enumerate(n, Scan); }
public double[] Double(int n) { return enumerate(n, Double); }
public int[] Integer(int n) { return enumerate(n, Integer); }
public long[] Long(int n) { return enumerate(n, Long); }
}
}
static class Ex
{
static public string AsString(this IEnumerable<char> ie) { return new string(System.Linq.Enumerable.ToArray(ie)); }
static public string AsJoinedString<T>(this IEnumerable<T> ie, string st = " ") { return string.Join(st, ie); }
static public void Main()
{
var solver = new Program.Solver();
solver.Solve();
Program.IO.Printer.Out.Flush();
}
}
#endregion
#region sieve
static public partial class MathEx
{
static public bool[] Sieve(int p)
{
var isPrime = new bool[p + 1];
for (int i = 2; i <= p; i++) isPrime[i] = true;
for (int i = 2; i * i <= p; i++)
if (!isPrime[i]) continue;
else
for (int j = i * i; j <= p; j += i)
isPrime[j] = false;
return isPrime;
}
}
#endregion
#region DisjointSet
public class DisjointSet
{
public int[] par, ranks, count;
public DisjointSet(int n)
{
par = new int[n];
count = new int[n];
for (int i = 0; i < n; i++)
{
par[i] = i;
count[i] = 1;
}
ranks = new int[n];
}
public int this[int id] { get { return (par[id] == id) ? id : this[par[id]]; } }
public bool Unite(int x, int y)
{
x = this[x]; y = this[y];
if (x == y) return false;
if (ranks[x] < ranks[y])
{
par[x] = y;
count[y] += count[x];
}
else
{
par[y] = x;
count[x] += count[y];
if (ranks[x] == ranks[y])
ranks[x]++;
}
return true;
}
public int Size(int x) { return count[this[x]]; }
public bool IsUnited(int x, int y) { return this[x] == this[y]; }
}
#endregion