結果
問題 | No.719 Coprime |
ユーザー | EmKjp |
提出日時 | 2019-06-10 08:35:38 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 6,916 bytes |
コンパイル時間 | 1,124 ms |
コンパイル使用メモリ | 116,612 KB |
実行使用メモリ | 29,732 KB |
最終ジャッジ日時 | 2024-10-06 00:31:42 |
合計ジャッジ時間 | 6,612 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 36 ms
25,592 KB |
testcase_01 | AC | 33 ms
25,488 KB |
testcase_02 | AC | 32 ms
25,324 KB |
testcase_03 | AC | 32 ms
25,588 KB |
testcase_04 | AC | 33 ms
25,388 KB |
testcase_05 | AC | 32 ms
25,708 KB |
testcase_06 | AC | 34 ms
25,516 KB |
testcase_07 | AC | 34 ms
27,504 KB |
testcase_08 | AC | 33 ms
27,376 KB |
testcase_09 | AC | 34 ms
27,624 KB |
testcase_10 | AC | 33 ms
27,656 KB |
testcase_11 | AC | 36 ms
27,780 KB |
testcase_12 | AC | 34 ms
25,456 KB |
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 | AC | 33 ms
25,352 KB |
testcase_26 | WA | - |
testcase_27 | WA | - |
testcase_28 | WA | - |
testcase_29 | WA | - |
testcase_30 | AC | 34 ms
25,712 KB |
testcase_31 | AC | 33 ms
25,584 KB |
testcase_32 | AC | 36 ms
23,348 KB |
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 | - |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System; using System.IO; using System.Collections.Generic; using System.Globalization; using System.Linq; using System.Text; using E = System.Linq.Enumerable; partial class Solver { const int Mod = 1000000007; public void Run() { var N = ni(); var primeSet = new PrimeSet(1263); var factor = primeSet .Select(p => GetFactor(p, N)) .Where(p => p.Count > 0) .ToArray(); var f1 = factor.Where(f => f.Count >= 2).ToArray(); var f2 = factor.Where(f => f.Count < 2).ToArray(); var M = f1.Length; var maxV = new int[1 << M]; var vList = E.Range(0, 1 << M).Select(_ => new List<int>()).ToArray(); for (int i = 1; i <= N; i++) { var v = i; int flags = 0; for (int j = 0; j < f1.Length; j++) { var p = f1[j].Prime; if (v % p == 0) { flags |= (1 << j); while (v % p == 0) v /= p; } } if (v > 1) continue; maxV[flags] = i; vList[flags].Add(i); } var dp1 = new int[1 << M]; for (int i = 1; i < dp1.Length; i++) { dp1[i] = int.MinValue; for (int j = i; j > 0; j = (j - 1) & i) { var pre = i ^ j; dp1[i] = Math.Max(dp1[i], dp1[pre] + maxV[j]); } } var dp2 = new int[1 << M]; foreach (var p in f2) { var next = new int[1 << M]; for (int i = 0; i < dp2.Length; i++) { next[i] = dp2[i] + p.Prime; for (int j = i; j > 0; j = (j - 1) & i) { var v = 0; for (int k = vList[j].Count - 1; k >= 0; k--) { if (vList[j][k] * p.Prime <= N) { v = vList[j][k]; break; } } next[i] = Math.Max(next[i], dp2[i ^ j] + v); } } dp2 = next; } long ans = 0; for (int i = 0; i < (1 << M); i++) { ans = Math.Max(ans, dp1[i] + dp2[((1 << M) - 1) ^ i]); } cout.WriteLine(ans); } Factor GetFactor(int prime, int N) { int cnt = 0; long x = prime; while (x <= N) { x *= prime; cnt++; } return new Factor { Prime = prime, Count = cnt }; } struct Factor { public int Prime { get; set; } public int Count { get; set; } } } public class PrimeSet : List<int> { private readonly bool[] isPrime; public PrimeSet(int size) : base() { isPrime = Enumerable.Repeat(true, size).ToArray(); Add(2); for (int i = 3; i <= size; i += 2) { if (!isPrime[i >> 1]) continue; Add(i); for (long j = (long)i * i; j <= size; j += i + i) isPrime[j >> 1] = false; } } public bool IsPrime(long x) { if (x == 2) return true; if (x <= 1 || x % 2 == 0) return false; return isPrime[x >> 1]; } } // PREWRITEN CODE BEGINS FROM HERE partial class Solver : Scanner { public static void Main(string[] args) { #if LOCAL new Solver(Console.In, Console.Out).Run(); #else Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false }); new Solver(Console.In, Console.Out).Run(); Console.Out.Flush(); #endif } #pragma warning disable IDE0052 private readonly TextReader cin; private readonly TextWriter cout; #pragma warning restore IDE0052 public Solver(TextReader reader, TextWriter writer) : base(reader) { this.cin = reader; this.cout = writer; } public Solver(string input, TextWriter writer) : this(new StringReader(input), writer) { } #pragma warning disable IDE1006 #pragma warning disable IDE0051 private int ni() { return NextInt(); } private int[] ni(int n) { return NextIntArray(n); } private long nl() { return NextLong(); } private long[] nl(int n) { return NextLongArray(n); } private double nd() { return NextDouble(); } private double[] nd(int n) { return NextDoubleArray(n); } private string ns() { return Next(); } private string[] ns(int n) { return NextArray(n); } #pragma warning restore IDE1006 #pragma warning restore IDE0051 } public static class LinqPadExtension { static public T Dump<T>(this T obj) { #if LOCAL return LINQPad.Extensions.Dump(obj); #else return obj; #endif } } public class Scanner { private readonly TextReader Reader; private readonly Queue<string> TokenQueue = new Queue<string>(); private readonly CultureInfo ci = CultureInfo.InvariantCulture; public Scanner() : this(Console.In) { } public Scanner(TextReader reader) { this.Reader = reader; } public int NextInt() { return int.Parse(Next(), ci); } public long NextLong() { return long.Parse(Next(), ci); } public double NextDouble() { return double.Parse(Next(), ci); } public string[] NextArray(int size) { var array = new string[size]; for (int i = 0; i < size; i++) array[i] = Next(); return array; } public int[] NextIntArray(int size) { var array = new int[size]; for (int i = 0; i < size; i++) array[i] = NextInt(); return array; } public long[] NextLongArray(int size) { var array = new long[size]; for (int i = 0; i < size; i++) array[i] = NextLong(); return array; } public double[] NextDoubleArray(int size) { var array = new double[size]; for (int i = 0; i < size; i++) array[i] = NextDouble(); return array; } public string Next() { if (TokenQueue.Count == 0) { if (!StockTokens()) throw new InvalidOperationException(); } return TokenQueue.Dequeue(); } public bool HasNext() { if (TokenQueue.Count > 0) return true; return StockTokens(); } static readonly char[] _separator = new[] { ' ' }; private bool StockTokens() { while (true) { var line = Reader.ReadLine(); if (line == null) return false; var tokens = line.Split(_separator, StringSplitOptions.RemoveEmptyEntries); if (tokens.Length == 0) continue; foreach (var token in tokens) TokenQueue.Enqueue(token); return true; } } }