結果

問題 No.375 立方体のN等分 (1)
ユーザー eitaho
提出日時 2016-06-04 23:34:36
言語 C#
(csc 2.7.0.62620)
結果
AC  
実行時間 283 ms
コード長 3,964 Byte
コンパイル時間 1,149 ms
使用メモリ 40,580 KB
最終ジャッジ日時 2018-07-14 21:30:58

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
sample1.txt AC 30 ms
13,276 KB
sample2.txt AC 31 ms
13,300 KB
system_test1.txt AC 35 ms
17,376 KB
t01.txt AC 31 ms
13,268 KB
t02.txt AC 31 ms
15,316 KB
t03.txt AC 31 ms
15,316 KB
t04.txt AC 31 ms
15,320 KB
t05.txt AC 32 ms
15,332 KB
t06.txt AC 51 ms
21,620 KB
t07.txt AC 32 ms
17,360 KB
t08.txt AC 31 ms
15,320 KB
t09.txt AC 30 ms
13,288 KB
t10.txt AC 31 ms
13,280 KB
t11.txt AC 32 ms
17,372 KB
t12.txt AC 85 ms
25,160 KB
t13.txt AC 32 ms
13,280 KB
t14.txt AC 32 ms
17,368 KB
t15.txt AC 156 ms
30,860 KB
t16.txt AC 83 ms
24,952 KB
t17.txt AC 33 ms
17,364 KB
t18.txt AC 32 ms
17,368 KB
t19.txt AC 31 ms
13,276 KB
t20.txt AC 283 ms
40,580 KB
t21.txt AC 32 ms
11,240 KB
t22.txt AC 31 ms
15,320 KB
t23.txt AC 33 ms
13,292 KB
t24.txt AC 34 ms
15,316 KB
t25.txt AC 32 ms
15,328 KB
t26.txt AC 34 ms
17,356 KB
t27.txt AC 36 ms
17,364 KB
t28.txt AC 33 ms
13,272 KB
t29.txt AC 33 ms
15,320 KB
t30.txt AC 34 ms
17,360 KB
t31.txt AC 31 ms
13,276 KB
テストケース一括ダウンロード
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 2.6.0.62309 (d3f6b8e7)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff #
using System;
using System.IO;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using System.Collections.Generic;
using System.Diagnostics;
using System.Numerics;
using Enu = System.Linq.Enumerable;

public class Program
{
    long ans;
    long[] primes;
    int[] num;
    long[] mult = { 1, 1, 1 };

    public void Solve()
    {
        long N = Reader.Long();
        ans = N - 1;
        var factors = Factorization(N);
        primes = factors.Keys.ToArray();
        num = factors.Values.ToArray();
        Rec(0, 0);
        Console.WriteLine(ans + " " + (N - 1));
        Console.ReadLine();
    }

    void Rec(int who, long sum)
    {
        if (who == 2)
        {
            long mult = 1;
            for (int i = 0; i < primes.Length; i++)
                for (int c = 0; c < num[i]; c++)
                    mult *= primes[i];
            sum += mult - 1;
            if (sum < ans) ans = sum;
            return;
        }
        var cand = new List<int[]>();
        Select(0, new int[primes.Length], cand);
        foreach (var c in cand)
        {
            long mult = 1;
            for (int i = 0; i < primes.Length; i++)
            {
                num[i] -= c[i];
                for (int t = 0; t < c[i]; t++) mult *= primes[i];
            }
            Rec(who + 1, sum + mult - 1);
            for (int i = 0; i < primes.Length; i++)
                num[i] += c[i];
        }
    }

    void Select(int i, int[] curr, List<int[]> cand)
    {
        if (i == primes.Length)
        {
            int[] copy = new int[curr.Length];
            Array.Copy(curr, copy, curr.Length);
            cand.Add(copy);
            return;
        }
        for (int c = 0; c <= num[i]; c++)
        {
            curr[i] = c;
            Select(i + 1, curr, cand);
        }
    }


    static Dictionary<long, int> Factorization(long n)
    {
        var dic = new Dictionary<long, int>();
        for (long i = 2; i * i <= n; i++)
            while (n % i == 0)
            {
                n /= i;
                if (!dic.ContainsKey(i)) dic[i] = 1;
                else dic[i]++;
            }
        if (n > 1) dic[n] = 1;
        return dic;
    }
}


class Entry { static void Main() { new Program().Solve(); } }
class Reader
{
    static TextReader reader = Console.In;
    static readonly char[] separator = { ' ' };
    static readonly StringSplitOptions op = StringSplitOptions.RemoveEmptyEntries;
    static string[] A = new string[0];
    static int i;
    static void Init() { A = new string[0]; }
    public static void Set(TextReader r) { reader = r; Init(); }
    public static void Set(string file) { reader = new StreamReader(file); Init(); }
    public static bool HasNext() { return CheckNext(); }
    public static string String() { return Next(); }
    public static int Int() { return int.Parse(Next()); }
    public static long Long() { return long.Parse(Next()); }
    public static double Double() { return double.Parse(Next()); }
    public static int[] IntLine() { return Array.ConvertAll(Split(Line()), int.Parse); }
    public static int[] IntArray(int N) { return Range(N, Int); }
    public static int[][] IntTable(int H) { return Range(H, IntLine); }
    public static string[] StringArray(int N) { return Range(N, Next); }
    public static string[][] StringTable(int N) { return Range(N, () => Split(Line())); }
    public static string Line() { return reader.ReadLine().Trim(); }
    static T[] Range<T>(int N, Func<T> f) { return Enu.Range(0, N).Select(i => f()).ToArray(); }
    static string[] Split(string s) { return s.Split(separator, op); }
    static string Next() { CheckNext(); return A[i++]; }
    static bool CheckNext()
    {
        if (i < A.Length) return true;
        string line = reader.ReadLine();
        if (line == null) return false;
        if (line == "") return CheckNext();
        A = Split(line);
        i = 0;
        return true;
    }
}
0