結果
| 問題 |
No.3250 最小公倍数
|
| ユーザー |
 kakel-san
|
| 提出日時 | 2025-08-29 23:07:58 |
| 言語 | C# (.NET 8.0.404) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 8,776 bytes |
| コンパイル時間 | 10,093 ms |
| コンパイル使用メモリ | 170,368 KB |
| 実行使用メモリ | 213,160 KB |
| 最終ジャッジ日時 | 2025-08-29 23:08:37 |
| 合計ジャッジ時間 | 32,985 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 18 TLE * 1 -- * 2 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (110 ミリ秒)。 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[] NList => ReadLine().Split().Select(int.Parse).ToArray();
static int[][] NArr(long n) => Enumerable.Repeat(0, (int)n).Select(_ => NList).ToArray();
static int[] NMi => ReadLine().Split().Select(c => int.Parse(c) - 1).ToArray();
static int[][] NMap(int n) => Enumerable.Repeat(0, n).Select(_ => NMi).ToArray();
static string[] SList(long n) => Enumerable.Repeat(0, (int)n).Select(_ => ReadLine()).ToArray();
public static void Main()
{
Solve();
// Test();
}
static void Test()
{
var dp = Enumerable.Repeat(true, 1_000_001).ToArray();
for (var i = 2; i < dp.Length; ++i)
{
if (!dp[i]) continue;
for (var j = i * 2; j < dp.Length; j += i) dp[j] = false;
}
var plist = new List<int>();
for (var i = 2; i < dp.Length; ++i) if (dp[i]) plist.Add(i);
var r = new Random();
var n = 500000;
var a = new int[n];
for (var i = 0; i < n; ++i) a[i] = r.Next(1_000_000) + 1;
// for (var i = 0; i < n; ++i) a[i] = 510510;
// for (var i = 0; i < n; ++i) a[i] = plist[r.Next(plist.Count)];
for (var i = 0; i < n; ++i)
{
while (true)
{
var m = r.Next(10);
if (a[i] * plist[m] > 1_000_000) break;
a[i] *= plist[m];
}
}
var map = new int[n - 1][];
for (var i = 0; i < map.Length; ++i) map[i] = new int[] { r.Next(i + 1), i + 1 };
// for (var i = 0; i < map.Length; ++i) map[i] = new int[] { i / 2, i + 1 };
// for (var i = 0; i < map.Length; ++i) map[i] = new int[] { i, i + 1 };
var start = DateTime.Now;
var ans = LCM(n, a, map);
WriteLine(string.Join(" ", ans.Take(10)));
WriteLine((DateTime.Now - start).TotalSeconds);
}
static void Solve()
{
var n = NN;
var a = NList;
var map = NMap(n - 1);
var ans = LCM(n, a, map);
WriteLine(string.Join("\n", ans));
}
static long[] LCM(int n, int[] a, int[][] map)
{
var tree = new List<int>[n];
for (var i = 0; i < n; ++i) tree[i] = new List<int>();
foreach (var edge in map)
{
tree[edge[0]].Add(edge[1]);
tree[edge[1]].Add(edge[0]);
}
var dep = Enumerable.Repeat(-1, n).ToArray();
dep[0] = 0;
var q = new Queue<int>();
q.Enqueue(0);
var plist = new int[n];
plist[0] = -1;
while (q.Count > 0)
{
var cur = q.Dequeue();
foreach (var next in tree[cur])
{
if (dep[next] >= 0) continue;
dep[next] = dep[cur] + 1;
plist[next] = cur;
q.Enqueue(next);
}
}
var sorted = new List<(int id, int dep, int prev)>(n);
for (var i = 1; i < n; ++i) sorted.Add((i, dep[i], plist[i]));
sorted.Sort((l, r) => r.dep.CompareTo(l.dep));
var minlist = GetMinPDivList(1_000_000);
var dlist = new Dictionary<int, int>[n];
var ans = new long[n];
for (var i = 0; i < n; ++i)
{
dlist[i] = PDiv(a[i], minlist);
ans[i] = a[i];
}
foreach (var si in sorted)
{
var prev = si.prev;
if (dep[prev] < si.dep)
{
if (dlist[prev].Count > dlist[si.id].Count)
{
foreach (var kv in dlist[si.id])
{
if (dlist[prev].ContainsKey(kv.Key))
{
if (dlist[prev][kv.Key] < kv.Value)
{
ans[prev] = ans[prev] * Exp(kv.Key, kv.Value - dlist[prev][kv.Key]) % mod;
dlist[prev][kv.Key] = kv.Value;
}
}
else
{
ans[prev] = ans[prev] * Exp(kv.Key, kv.Value) % mod;
dlist[prev][kv.Key] = kv.Value;
}
}
}
else
{
var lcm = ans[si.id];
var d = dlist[si.id];
foreach (var kv in dlist[prev])
{
if (d.ContainsKey(kv.Key))
{
if (d[kv.Key] < kv.Value)
{
lcm = lcm * Exp(kv.Key, kv.Value - d[kv.Key]) % mod;
d[kv.Key] = kv.Value;
}
}
else
{
lcm = lcm * Exp(kv.Key, kv.Value) % mod;
d[kv.Key] = kv.Value;
}
}
ans[prev] = lcm;
dlist[prev] = d;
}
}
}
return ans;
}
static int mod = 998_244_353;
static Dictionary<int, int> DFS(int cur, int prev, int[] a, List<int>[] tree, int[] minlist, long[] ans)
{
var dic = PDiv(a[cur], minlist);
ans[cur] = a[cur];
foreach (var next in tree[cur])
{
if (next == prev) continue;
var ndic = DFS(next, cur, a, tree, minlist, ans);
if (dic.Count > ndic.Count)
{
foreach (var kv in ndic)
{
if (dic.ContainsKey(kv.Key))
{
if (dic[kv.Key] < kv.Value)
{
ans[cur] = ans[cur] * Exp(kv.Key, kv.Value - dic[kv.Key]) % mod;
dic[kv.Key] = kv.Value;
}
}
else
{
ans[cur] = ans[cur] * Exp(kv.Key, kv.Value) % mod;
dic[kv.Key] = kv.Value;
}
}
}
else
{
ans[cur] = ans[next];
foreach (var kv in dic)
{
if (ndic.ContainsKey(kv.Key))
{
if (ndic[kv.Key] < kv.Value)
{
ans[cur] = ans[cur] * Exp(kv.Key, kv.Value - ndic[kv.Key]) % mod;
ndic[kv.Key] = kv.Value;
}
}
else
{
ans[cur] = ans[cur] * Exp(kv.Key, kv.Value) % mod;
ndic[kv.Key] = kv.Value;
}
}
dic = ndic;
}
}
return dic;
}
static void DebugDic<T, U>(Dictionary<T, U> dic)
{
Console.WriteLine("Dic:");
foreach (var kv in dic) Console.WriteLine(" {0} = {1}", kv.Key, kv.Value);
}
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 Dictionary<int, int> PDiv(int n, int[] minPDivList)
{
var p = minPDivList[n];
if (n == p)
{
var dic = new Dictionary<int, int>();
dic.Add(p, 1);
return dic;
}
else
{
var dic = PDiv(n / p, minPDivList);
if (dic.ContainsKey(p)) ++dic[p];
else dic.Add(p, 1);
return dic;
}
}
static long Exp(long n, long p)
{
long _n = n % mod;
var _p = p;
var result = 1L;
if ((_p & 1) == 1) result *= _n;
while (_p > 0)
{
_n = _n * _n % mod;
_p >>= 1;
if ((_p & 1) == 1) result = result * _n % mod;
}
return result;
}
}