結果
問題 |
No.16 累乗の加算
|
ユーザー |
![]() |
提出日時 | 2016-03-31 15:28:58 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 34 ms / 5,000 ms |
コード長 | 2,070 bytes |
コンパイル時間 | 1,081 ms |
コンパイル使用メモリ | 105,600 KB |
実行使用メモリ | 21,632 KB |
最終ジャッジ日時 | 2024-06-26 05:12:16 |
合計ジャッジ時間 | 2,201 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 14 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System; using System.Collections; using System.Collections.Generic; using System.Text; public class Program { public void Proc() { Reader.IsDebug = false; int[] inpt = Reader.GetInt(); int baseNum = inpt[0]; int itemCount = inpt[1]; int[] powList = Reader.GetInt(); long ans = 0; foreach (int pow in powList) { ans += this.GetSubTotal(baseNum, pow); ans = ans % Div; } Console.WriteLine(ans); } private long GetSubTotal(int baseNum, int pow) { if(dic[pow] > 0) { return dic[pow]; } long ans = 1; if(pow <= 4) { ans = (long)Math.Pow(baseNum, pow) % Div; } else { int half = pow / 2; ans = this.GetSubTotal(baseNum, half); ans = ans * this.GetSubTotal(baseNum, pow - half) % Div; } dic[pow] = ans; return ans; } private long[] dic = new long[100000000 + 1]; private int Div = 1000003; public class Reader { private static String InitText = @" "; private static System.IO.StringReader sr = null; public static bool IsDebug = true; public static string ReadLine() { if(IsDebug) { if(sr == null) { sr = new System.IO.StringReader(InitText.Trim()); } return sr.ReadLine(); } else { return Console.ReadLine(); } } public static int[] GetInt(char delimiter = ' ') { string[] inpt = ReadLine().Split(delimiter); int[] ret = new int[inpt.Length]; for(int i=0; i<inpt.Length; i++) { ret[i] = int.Parse(inpt[i]); } return ret; } } public static void Main(string[] args) { Program prg = new Program(); prg.Proc(); } }