結果
問題 | No.1529 Constant Lcm |
ユーザー | KumaTachiRen |
提出日時 | 2022-01-31 16:27:50 |
言語 | C# (.NET 8.0.203) |
結果 |
AC
|
実行時間 | 54 ms / 3,000 ms |
コード長 | 4,741 bytes |
コンパイル時間 | 9,983 ms |
コンパイル使用メモリ | 166,092 KB |
実行使用メモリ | 185,388 KB |
最終ジャッジ日時 | 2024-06-11 08:58:46 |
合計ジャッジ時間 | 12,183 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 35 ms
23,008 KB |
testcase_01 | AC | 34 ms
22,784 KB |
testcase_02 | AC | 33 ms
22,656 KB |
testcase_03 | AC | 34 ms
22,912 KB |
testcase_04 | AC | 34 ms
22,912 KB |
testcase_05 | AC | 33 ms
23,040 KB |
testcase_06 | AC | 38 ms
22,784 KB |
testcase_07 | AC | 38 ms
22,656 KB |
testcase_08 | AC | 38 ms
23,168 KB |
testcase_09 | AC | 38 ms
22,764 KB |
testcase_10 | AC | 45 ms
24,064 KB |
testcase_11 | AC | 41 ms
23,552 KB |
testcase_12 | AC | 35 ms
23,424 KB |
testcase_13 | AC | 41 ms
23,936 KB |
testcase_14 | AC | 39 ms
23,936 KB |
testcase_15 | AC | 41 ms
23,808 KB |
testcase_16 | AC | 38 ms
23,680 KB |
testcase_17 | AC | 37 ms
23,424 KB |
testcase_18 | AC | 39 ms
23,660 KB |
testcase_19 | AC | 41 ms
23,808 KB |
testcase_20 | AC | 46 ms
24,300 KB |
testcase_21 | AC | 45 ms
24,064 KB |
testcase_22 | AC | 54 ms
24,064 KB |
testcase_23 | AC | 44 ms
23,936 KB |
testcase_24 | AC | 44 ms
24,312 KB |
testcase_25 | AC | 44 ms
185,388 KB |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (103 ms)。 MSBuild のバージョン 17.9.6+a4ecab324 (.NET) /home/judge/data/code/Main.cs(87,10): warning CS0414: フィールド 'Solver.inf' が割り当てられていますが、値は使用されていません [/home/judge/data/code/main.csproj] main -> /home/judge/data/code/bin/Release/net8.0/main.dll main -> /home/judge/data/code/bin/Release/net8.0/publish/
ソースコード
using System; using System.Linq; using System.Numerics; using System.Collections; using System.Collections.Generic; using System.IO; using System.Text; using N = System.Int64; static class Program { static public void Main(string[] args) { Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false }); var solver = new Solver(); solver.Solve(); Console.Out.Flush(); } } public class Solver { public void Solve() { int n = ri; if (n == 2) { Write(1); return; } else if (n == 3) { Write(2); return; } else if (n == 4) { Write(12); return; } ModInt ans = 1; var isprime = new bool[n]; for (int i = 2; i < n; i++) isprime[i] = true; for (int p = 2; p < n; p++) { if (!isprime[p]) continue; for (int j = p * 2; j < n; j += p) isprime[j] = false; N pow = 1; N k = 1; while (n % (pow * p) == 0) { k = k * p * p; pow *= p; } if (pow == n) k = k / p / p; else { N m = n / pow; pow = 1; while (pow * p < m) { k = k * p; pow *= p; } } ans *= k; } Write(ans); } struct ModInt { private const long _mod = 998244353; long Val; public ModInt(long v) { Val = v; } public override string ToString() { return Val.ToString(); } public static implicit operator ModInt(long n) { long r = n % _mod; return new ModInt(r < 0 ? r + _mod : r); } public static ModInt operator +(ModInt a, ModInt b) { long r = a.Val + b.Val; return new ModInt(r < _mod ? r : r - _mod); } public static ModInt operator -(ModInt a, ModInt b) { long r = a.Val - b.Val; return new ModInt(r < 0 ? r + _mod : r); } public static ModInt operator -(ModInt a) { return new ModInt(a.Val == 0 ? 0 : _mod - a.Val); } public static ModInt operator *(ModInt a, ModInt b) { return new ModInt(a.Val * b.Val % _mod); } public static ModInt operator /(ModInt a, ModInt b) { return a * b.Inv; } public static ModInt Pow(ModInt b, long n) { long t = b.Val, r = 1; while (n > 0) { if ((n & 1) == 1) r = r * t % _mod; t = t * t % _mod; n >>= 1; } return new ModInt(r); } public ModInt Inv { get { return Pow(Val, _mod - 2); } } } long inf = (long)1 << 60; int ri { get { return (int)sc.Integer(); } } long rl { get { return sc.Integer(); } } double rd { get { return sc.Double(); } } string rs { get { return sc.Scan(); } } public StreamScanner sc = new StreamScanner(Console.OpenStandardInput()); void WriteJoin<T>(string s, T[] t) { Console.WriteLine(string.Join(s, t)); } void WriteJoin<T>(string s, List<T> t) { Console.WriteLine(string.Join(s, t)); } void Write<T>(T t) { Console.WriteLine(t.ToString()); } void YN(bool t) { Console.WriteLine(t ? "YES" : "NO"); } void Yn(bool t) { Console.WriteLine(t ? "Yes" : "No"); } void yn(bool t) { Console.WriteLine(t ? "yes" : "no"); } } public class StreamScanner { public StreamScanner(Stream stream) { str = stream; } private readonly Stream str; private readonly byte[] buf = new byte[1024]; private int len, ptr; public bool isEof = false; public bool IsEndOfStream { get { return isEof; } } private byte read() { if (isEof) throw new EndOfStreamException(); if (ptr >= len) { ptr = 0; if ((len = str.Read(buf, 0, 1024)) <= 0) { isEof = true; return 0; } } return buf[ptr++]; } public char Char() { byte b = 0; do b = read(); while (b < 33 || 126 < b); return (char)b; } public string Scan() { var sb = new StringBuilder(); for (var b = Char(); b >= 33 && b <= 126; b = (char)read()) sb.Append(b); return sb.ToString(); } public long Integer() { long ret = 0; byte b = 0; var ng = false; do b = read(); while (b != '-' && (b < '0' || '9' < b)); if (b == '-') { ng = true; b = read(); } for (; true; b = read()) { if (b < '0' || '9' < b) return ng ? -ret : ret; else ret = ret * 10 + b - '0'; } } public double Double() { return double.Parse(Scan()); } }