結果

問題 No.442 和と積
コンテスト
ユーザー norioc
提出日時 2016-11-12 15:39:17
言語 C#(csc)
(csc 3.9.0)
結果
TLE  
実行時間 -
コード長 2,080 bytes
コンパイル時間 2,926 ms
コンパイル使用メモリ 115,472 KB
実行使用メモリ 49,100 KB
最終ジャッジ日時 2024-11-25 20:26:05
合計ジャッジ時間 10,340 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15 TLE * 3
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

using System;
using System.Collections.Generic;
using System.Linq;

static class Ext {
    public static Dictionary<T, int> Frequencies<T>(this IEnumerable<T> xs) {
        var d = new Dictionary<T, int>();
        foreach (var x in xs) {
            if (!d.ContainsKey(x))
                d[x] = 1;
            else
                d[x]++;
        }
        return d;
    }

    public static U GetOrDefault<T, U>(this Dictionary<T, U> dict, T key, U val = default(U)) {
        U x;
        return dict.TryGetValue(key, out x) ? x : val;
    }
}

class Program {
    static int ReadInt() { return int.Parse(Console.ReadLine()); }
    static int[] ReadInts() { return Console.ReadLine().Split().Select(int.Parse).ToArray(); }
    static string[] ReadStrings() { return Console.ReadLine().Split(); }

    static long Pow(long x, int n) {
        if (n == 0) return 1;
        if ((n & 1) == 0) return Pow(x * x, n / 2);
        return x * Pow(x, n - 1);
    }

    static List<long> Fac(long n) {
        var factors = new List<long>();
        while (n % 2 == 0) {
            factors.Add(2);
            n /= 2;
        }

        long m = (long)Math.Sqrt(n);
        for (int i = 3; i <= m; i += 2) {
            while (n % i == 0) {
                factors.Add(i);
                n /= i;
            }
            if (i > n) break;
        }
        if (n > 1) factors.Add(n);
        return factors;
    }

    static long Calc(long a, long b) {
        var freq = Fac(a + b).Frequencies();

        var ad = Fac(a).Frequencies();
        var bd = Fac(b).Frequencies();
        foreach (var k in ad.Keys.Union(bd.Keys).ToArray()) {
            ad[k] = ad.GetOrDefault(k) +  bd.GetOrDefault(k);
        }

        long ans = 1;
        foreach (var k in freq.Keys) {
            int n = Math.Min(freq[k], ad.GetOrDefault(k));
            ans *= Pow(k, n);
        }
        return ans;
    }

    static void Main() {
        var ab = Console.ReadLine().Split().Select(long.Parse).ToArray();
        long a = ab[0], b = ab[1];

        Console.WriteLine(Calc(a, b));
    }
}
0