結果
問題 | No.2249 GCDistance |
ユーザー |
|
提出日時 | 2023-03-17 23:26:42 |
言語 | C# (.NET 8.0.404) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,312 bytes |
コンパイル時間 | 7,710 ms |
コンパイル使用メモリ | 166,660 KB |
実行使用メモリ | 396,092 KB |
最終ジャッジ日時 | 2024-09-18 12:31:10 |
合計ジャッジ時間 | 68,299 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | TLE * 1 |
other | AC * 10 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (82 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/
ソースコード
using System;using static System.Console;using System.Linq;using System.Collections.Generic;class Program{static int NN => int.Parse(ReadLine());static int[] LList(int n) => Enumerable.Repeat(0, n).Select(_ => int.Parse(ReadLine())).ToArray();public static void Main(){Solve();}static void Solve(){var t = NN;var a = LList(t);WriteLine(string.Join("\n", GCDistance(a)));}static long[] GCDistance(int[] a){var max = 10_000_001;var phis = Phis(max);var cum = new long[max];for (var i = 1; i < cum.Length; ++i){cum[i] = cum[i - 1] + phis[i];}var ans = new long[a.Length];for (var i = 0; i < a.Length; ++i){ans[i] = (long)a[i] * (a[i] - 1) - cum[a[i]];}return ans;}static int[] Phis(int max){var ans = new int[max + 1];var minPDivList = GetMinPDivList(max);for (var i = 1; i < ans.Length; ++i){var p = PDiv(i, minPDivList).Distinct();var phi = i;foreach (var pi in p) phi = phi / pi * (pi - 1);ans[i] = phi;}return ans;}static int[] GetMinPDivList(int max){var minPDivList = new int[max + 1];for (var i = 0; i <= max; ++i) minPDivList[i] = i;for (var i = 2; i * i <= max; ++i) if (minPDivList[i] == i){for (var j = i * i; j <= max; j += i) if (minPDivList[j] == j){minPDivList[j] = i;}}return minPDivList;}static int GetMinPDiv(int n, int min){var p = min;while ((long)p * p <= n){if (n % p == 0) return p;++p;}return n;}static List<int> PDiv(int n, int[] minPDivList){var p = minPDivList[n];if (n == p){var dic = new List<int>();dic.Add(p);return dic;}else{var dic = PDiv(n / p, minPDivList);dic.Add(p);return dic;}}}