結果

問題 No.1498 Factorization from -1 to 1
ユーザー kzrnmkzrnm
提出日時 2021-05-06 19:56:58
言語 C#
(.NET 8.0.203)
結果
WA  
実行時間 -
コード長 13,711 bytes
コンパイル時間 16,873 ms
コンパイル使用メモリ 168,604 KB
実行使用メモリ 196,792 KB
最終ジャッジ日時 2024-09-14 11:16:50
合計ジャッジ時間 37,178 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 57 ms
28,544 KB
testcase_01 AC 58 ms
28,796 KB
testcase_02 WA -
testcase_03 AC 2,408 ms
55,040 KB
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 AC 105 ms
30,208 KB
testcase_11 AC 106 ms
30,080 KB
testcase_12 AC 105 ms
30,552 KB
testcase_13 AC 104 ms
30,464 KB
testcase_14 AC 105 ms
30,336 KB
testcase_15 AC 59 ms
28,800 KB
testcase_16 AC 59 ms
28,792 KB
testcase_17 WA -
testcase_18 AC 59 ms
28,928 KB
testcase_19 AC 59 ms
29,056 KB
testcase_20 AC 59 ms
29,056 KB
testcase_21 AC 59 ms
28,928 KB
testcase_22 AC 58 ms
196,792 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (98 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/

ソースコード

diff # 

using AtCoder.Internal;
using Kzrnm.Competitive;
using Kzrnm.Competitive.IO;
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Text;
partial class Program
{
    string YesNo(bool b) => b ? "Yes" : "No";
    const bool __ManyTestCases = true;
    [MethodImpl(MethodImplOptions.AggressiveOptimization)]
    private object Calc()
    {
        long q = cr;
        cw.WriteLineJoin(primes.PrimeFactoring(q * q + 1).SelectMany(t => Enumerable.Repeat(t.Key, t.Value)));
        return null;
    }
    PrimeNumber primes = new PrimeNumber(10002);
}
#region Expanded by https://github.com/naminodarie/SourceExpander
//LICENSE: https://github.com/naminodarie/Kzrnm.Competitive/blob/master/LICENSE
#pragma warning disable
namespace AtCoder.Internal{public class SimpleList<T>:IList<T>,IReadOnlyList<T>{private T[]data;private const int DefaultCapacity=2;public SimpleList(){data=new T[DefaultCapacity];}public SimpleList(int capacity){data=new T[Math.Max(capacity,DefaultCapacity)];}public SimpleList(IEnumerable<T>collection){if(collection is ICollection<T>col){data=new T[col.Count];col.CopyTo(data,0);Count=col.Count;}else{data=new T[DefaultCapacity];foreach(var item in collection)Add(item);}}public Memory<T>AsMemory()=>new Memory<T>(data,0,Count);public Span<T>AsSpan()=>new Span<T>(data,0,Count);public ref T this[int index]{[MethodImpl(MethodImplOptions.AggressiveInlining)]get{if((uint)index>=(uint)Count)ThrowIndexOutOfRangeException();return ref data[index];}}public int Count{get;private set;}public void Add(T item){if((uint)Count>=(uint)data.Length)Array.Resize(ref data,data.Length<<1);data[Count++]=item;}public void RemoveLast(){if( --Count<0)ThrowIndexOutOfRangeException();}public SimpleList<T>Reverse(){Array.Reverse(data,0,Count);return this;}public SimpleList<T>Reverse(int index,int count){Array.Reverse(data,index,count);return this;}public SimpleList<T>Sort(){Array.Sort(data,0,Count);return this;}public SimpleList<T>Sort(IComparer<T>comparer){Array.Sort(data,0,Count,comparer);return this;}public SimpleList<T>Sort(int index,int count,IComparer<T>comparer){Array.Sort(data,index,count,comparer);return this;}public void Clear()=>Count=0;public bool Contains(T item)=>IndexOf(item)>=0;public int IndexOf(T item)=>Array.IndexOf(data,item,0,Count);public void CopyTo(T[]array,int arrayIndex)=>Array.Copy(data,0,array,arrayIndex,Count);public T[]ToArray()=>AsSpan().ToArray();bool ICollection<T>.IsReadOnly=>false;T IList<T>.this[int index]{get=>data[index];set=>data[index]=value;}T IReadOnlyList<T>.this[int index]{get=>data[index];}void IList<T>.Insert(int index,T item)=>throw new NotSupportedException();bool ICollection<T>.Remove(T item)=>throw new NotSupportedException();void IList<T>.RemoveAt(int index)=>throw new NotSupportedException();IEnumerator IEnumerable.GetEnumerator()=>((IEnumerable<T>)this).GetEnumerator();IEnumerator<T>IEnumerable<T>.GetEnumerator(){for(int i=0;i<Count;i++)yield return data[i];}public Span<T>.Enumerator GetEnumerator()=>AsSpan().GetEnumerator();private static void ThrowIndexOutOfRangeException()=>throw new IndexOutOfRangeException();}}
namespace Kzrnm.Competitive.IO{public partial class ConsoleWriter:IDisposable{private const int DefaultBufferSize=1<<12;public StreamWriter StreamWriter{get;}public ConsoleWriter():this(Console.OpenStandardOutput(),Console.OutputEncoding,DefaultBufferSize){}public ConsoleWriter(Stream output,Encoding encoding):this(output,encoding,DefaultBufferSize){}public ConsoleWriter(Stream output,Encoding encoding,int bufferSize){StreamWriter=new StreamWriter(output,encoding,bufferSize);}public void Flush()=>StreamWriter.Flush();public ConsoleWriter WriteLine(){StreamWriter.WriteLine();return this;}public ConsoleWriter WriteLine<T>(T obj){StreamWriter.WriteLine(obj.ToString());return this;}public ConsoleWriter WriteLineJoin<T>(IEnumerable<T>col)=>WriteMany(' ',col);public ConsoleWriter WriteLineJoin<T1,T2>((T1,T2)tuple)=>WriteLineJoin(tuple.Item1,tuple.Item2);public ConsoleWriter WriteLineJoin<T1,T2,T3>((T1,T2,T3)tuple)=>WriteLineJoin(tuple.Item1,tuple.Item2,tuple.Item3);public ConsoleWriter WriteLineJoin<T1,T2,T3,T4>((T1,T2,T3,T4)tuple)=>WriteLineJoin(tuple.Item1,tuple.Item2,tuple.Item3,tuple.Item4);public ConsoleWriter WriteLineJoin<TTuple>(TTuple tuple)where TTuple:ITuple{var col=new object[tuple.Length];for(int i=0;i<col.Length;i++)col[i]=tuple[i];return WriteLineJoin(col);}public ConsoleWriter WriteLineJoin(params object[]col)=>WriteMany(' ',col);public ConsoleWriter WriteLineJoin<T1,T2>(T1 v1,T2 v2){StreamWriter.Write(v1.ToString());StreamWriter.Write(' ');StreamWriter.WriteLine(v2.ToString());return this;}public ConsoleWriter WriteLineJoin<T1,T2,T3>(T1 v1,T2 v2,T3 v3){StreamWriter.Write(v1.ToString());StreamWriter.Write(' ');StreamWriter.Write(v2.ToString());StreamWriter.Write(' ');StreamWriter.WriteLine(v3.ToString());return this;}public ConsoleWriter WriteLineJoin<T1,T2,T3,T4>(T1 v1,T2 v2,T3 v3,T4 v4){StreamWriter.Write(v1.ToString());StreamWriter.Write(' ');StreamWriter.Write(v2.ToString());StreamWriter.Write(' ');StreamWriter.Write(v3.ToString());StreamWriter.Write(' ');StreamWriter.WriteLine(v4.ToString());return this;}public ConsoleWriter WriteLines<T>(IEnumerable<T>col)=>WriteMany('\n',col);public ConsoleWriter WriteLineGrid<T>(IEnumerable<IEnumerable<T>>cols){foreach(var col in cols)WriteLineJoin(col);return this;}protected ConsoleWriter WriteMany<T>(char sep,IEnumerable<T>col){var en=col.GetEnumerator();if(!en.MoveNext())goto End;StreamWriter.Write(en.Current.ToString());while(en.MoveNext()){StreamWriter.Write(sep);StreamWriter.Write(en.Current.ToString());}End:StreamWriter.WriteLine();return this;}public void Dispose()=>Flush();}}
namespace Kzrnm.Competitive.IO{public partial class ConsoleWriter{public ConsoleWriter WriteLine(ReadOnlySpan<char>obj){StreamWriter.WriteLine(obj);return this;}public ConsoleWriter WriteLineJoin<T>(Span<T>col)=>WriteMany(' ',(ReadOnlySpan<T>)col);public ConsoleWriter WriteLineJoin<T>(ReadOnlySpan<T>col)=>WriteMany(' ',col);public ConsoleWriter WriteLines<T>(Span<T>col)=>WriteMany('\n',(ReadOnlySpan<T>)col);public ConsoleWriter WriteLines<T>(ReadOnlySpan<T>col)=>WriteMany('\n',col);protected ConsoleWriter WriteMany<T>(char sep,ReadOnlySpan<T>col){var en=col.GetEnumerator();if(!en.MoveNext())return this;StreamWriter.Write(en.Current.ToString());while(en.MoveNext()){StreamWriter.Write(sep);StreamWriter.Write(en.Current.ToString());}StreamWriter.WriteLine();return this;}}}
namespace Kzrnm.Competitive.IO{using static MethodImplOptions;public class PropertyConsoleReader{private const int BufSize=1<<12;private readonly Stream input;private readonly Encoding encoding;internal readonly byte[]buffer=new byte[BufSize];internal int pos=0;internal int len=0;public PropertyConsoleReader():this(Console.OpenStandardInput(),Console.InputEncoding){}public PropertyConsoleReader(Stream input,Encoding encoding){this.input=input;this.encoding=encoding;}[MethodImpl(AggressiveInlining)]protected internal byte Read(){if( ++pos>=len){if((len=input.Read(buffer,0,buffer.Length))<=0){buffer[0]=10;}pos=0;}return buffer[pos];}public int Int{[MethodImpl(AggressiveInlining)]get{int res=0;bool neg=false;byte b;do{b=Read();if(b=='-')neg=true;}while(b<'0');do{res=res*10+(b^'0');b=Read();}while('0'<=b);return neg?-res:res;}}public int Int0{[MethodImpl(AggressiveInlining)]get=>Int-1;}public uint UInt{[MethodImpl(AggressiveInlining)]get=>(uint)ULong;}public uint UInt0{[MethodImpl(AggressiveInlining)]get=>UInt-1;}public long Long{[MethodImpl(AggressiveInlining)]get{long res=0;bool neg=false;byte b;do{b=Read();if(b=='-')neg=true;}while(b<'0');do{res=res*10+(b^'0');b=Read();}while('0'<=b);return neg?-res:res;}}public long Long0{[MethodImpl(AggressiveInlining)]get=>Long-1;}public ulong ULong{[MethodImpl(AggressiveInlining)]get{ulong res=0;byte b;do b=Read();while(b<'0');do{res=res*10+(b^(ulong)'0');b=Read();}while('0'<=b);return res;}}public ulong ULong0{[MethodImpl(AggressiveInlining)]get=>ULong-1;}public string String{[MethodImpl(AggressiveInlining)]get{var sb=new List<byte>();;byte b;do b=Read();while(b<=' ');do{sb.Add(b);b=Read();}while(' '<b);return encoding.GetString(sb.ToArray());}}public string Ascii{[MethodImpl(AggressiveInlining)]get{var sb=new StringBuilder();byte b;do b=Read();while(b<=' ');do{sb.Append((char)b);b=Read();}while(' '<b);return sb.ToString();}}public string Line{[MethodImpl(AggressiveInlining)]get{var sb=new List<byte>();byte b;do b=Read();while(b<=' ');do{sb.Add(b);b=Read();}while(b!='\n'&&b!='\r');return encoding.GetString(sb.ToArray());}}public char Char{[MethodImpl(AggressiveInlining)]get{byte b;do b=Read();while(b<=' ');return(char)b;}}public double Double{[MethodImpl(AggressiveInlining)]get{return double.Parse(Ascii);}}public decimal Decimal{[MethodImpl(AggressiveInlining)]get{return decimal.Parse(Ascii);}}[MethodImpl(AggressiveInlining)]public static implicit operator int(PropertyConsoleReader cr)=>cr.Int;[MethodImpl(AggressiveInlining)]public static implicit operator uint(PropertyConsoleReader cr)=>cr.UInt;[MethodImpl(AggressiveInlining)]public static implicit operator long(PropertyConsoleReader cr)=>cr.Long;[MethodImpl(AggressiveInlining)]public static implicit operator ulong(PropertyConsoleReader cr)=>cr.ULong;[MethodImpl(AggressiveInlining)]public static implicit operator double(PropertyConsoleReader cr)=>cr.Double;[MethodImpl(AggressiveInlining)]public static implicit operator decimal(PropertyConsoleReader cr)=>cr.Decimal;[MethodImpl(AggressiveInlining)]public static implicit operator string(PropertyConsoleReader cr)=>cr.Ascii;}}
namespace System{public static class __CollectionExtension{public static TValue Get<TKey,TValue>(this IDictionary<TKey,TValue>dic,TKey key){dic.TryGetValue(key,out var v);return v;}public static(T Value,int Count)[]CompressCount<T>(this IEnumerable<T>collection){var e=collection.GetEnumerator();var list=new SimpleList<(T Value,int Count)>();if(!e.MoveNext())return Array.Empty<(T,int)>();var cur=e.Current;list.Add((cur,1));while(e.MoveNext()){if(EqualityComparer<T>.Default.Equals(cur,e.Current))list[^1].Count++;else{cur=e.Current;list.Add((cur,1));}}return list.ToArray();}}}
namespace Kzrnm.Competitive{public class PrimeNumber:ICollection<int>{readonly int[]primes;readonly int[]searches;public int Count=>primes.Length;public bool IsReadOnly=>true;public PrimeNumber(int max){(primes,searches)=Eratosthenes(max);}public Dictionary<long,int>PrimeFactoring(long num){var primeFactors=new Dictionary<long,int>();foreach(var p in EnumerateFactor(num)){primeFactors[p]=primeFactors.Get(p)+1;}return primeFactors;}public Dictionary<int,int>PrimeFactoring(int num){if(num<searches.Length)return PrimeFactoringFast(num);var primeFactors=new Dictionary<int,int>();foreach(var pl in EnumerateFactor(num)){var p=(int)pl;primeFactors[p]=primeFactors.Get(p)+1;}return primeFactors;}IEnumerable<long>EnumerateFactor(long num){foreach(var p in primes){if(num<2)break;while(DivIfMulti(ref num,p))yield return p;}if(num>1)yield return num;}static bool DivIfMulti(ref long num,long p){Math.DivRem(num,p,out var d);if(d==0){num/=p;return true;}return false;}Dictionary<int,int>PrimeFactoringFast(int num){if(num>=searches.Length)throw new ArgumentOutOfRangeException(nameof(num));var primeFactors=new Dictionary<int,int>();while(num>1){primeFactors[searches[num]]=primeFactors.Get(searches[num])+1;num/=searches[num];}return primeFactors;}static(int[]primes,int[]searches)Eratosthenes(int n){var searches=new int[n+1];Array.Copy(new int[11]{0,1,2,3,2,5,2,7,2,3,2},searches,Math.Min(11,searches.Length));var primes=new SimpleList<int>(n){2,3,5,7};if(n<11)return(primes.TakeWhile(p=>p<=n).ToArray(),searches);for(int i=11;i<searches.Length;i+=2){searches[i-1]=2;if(i%3==0)searches[i]=3;else if(i%5==0)searches[i]=5;else if(i%7==0)searches[i]=7;}if(n%2==0)searches[n]=2;var current=11;while(current*current<=n){primes.Add(current);var c2=current<<1;for(var i=current;i<searches.Length;i+=c2)if(searches[i]==0)searches[i]=current;while(searches[current]>0)current+=2;}for(var i=current;i<searches.Length;i+=2)if(searches[i]==0){searches[i]=i;primes.Add(i);}return(primes.ToArray(),searches);}public bool IsPrime(long num){if(num<=this.primes[^1])return Contains((int)num);foreach(var p in this)if(num%p==0)return false;return true;}public void Add(int item)=>throw new NotSupportedException();public void Clear()=>throw new NotSupportedException();public bool Contains(int item)=>Array.BinarySearch(primes,item)>=0;public void CopyTo(int[]array,int arrayIndex)=>primes.CopyTo(array,arrayIndex);public bool Remove(int item)=>throw new NotSupportedException();public ReadOnlySpan<int>.Enumerator GetEnumerator()=>new ReadOnlySpan<int>(primes).GetEnumerator();IEnumerator<int>IEnumerable<int>.GetEnumerator()=>((IEnumerable<int>)primes).GetEnumerator();IEnumerator IEnumerable.GetEnumerator()=>primes.GetEnumerator();}}
internal partial class Program{static void Main()=>new Program(new PropertyConsoleReader(),new ConsoleWriter()).Run();public PropertyConsoleReader cr;public ConsoleWriter cw;public Program(PropertyConsoleReader r,ConsoleWriter w){this.cr=r;this.cw=w;CultureInfo.CurrentCulture=CultureInfo.InvariantCulture;}public void Run(){int Q=__ManyTestCases?cr.Int:1;for(;Q>0;Q--){var res=Calc();if(res is double d)cw.WriteLine(d.ToString("0.####################",CultureInfo.InvariantCulture));else if(res is bool b)cw.WriteLine(YesNo(b));else if(res!=null&&res!=cw)cw.WriteLine(res.ToString());}cw.Flush();}}
#endregion Expanded by https://github.com/naminodarie/SourceExpander
0