結果
問題 | No.551 夏休みの思い出(2) |
ユーザー | kuuso1 |
提出日時 | 2017-01-08 03:55:29 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 2,543 bytes |
コンパイル時間 | 1,076 ms |
コンパイル使用メモリ | 116,236 KB |
実行使用メモリ | 25,696 KB |
最終ジャッジ日時 | 2024-05-09 23:12:48 |
合計ジャッジ時間 | 3,727 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | RE | - |
testcase_01 | RE | - |
testcase_02 | RE | - |
testcase_03 | RE | - |
testcase_04 | RE | - |
testcase_05 | RE | - |
testcase_06 | RE | - |
testcase_07 | RE | - |
testcase_08 | RE | - |
testcase_09 | RE | - |
testcase_10 | RE | - |
testcase_11 | RE | - |
testcase_12 | RE | - |
testcase_13 | RE | - |
testcase_14 | RE | - |
testcase_15 | RE | - |
testcase_16 | RE | - |
testcase_17 | RE | - |
testcase_18 | RE | - |
testcase_19 | RE | - |
testcase_20 | RE | - |
testcase_21 | RE | - |
testcase_22 | RE | - |
testcase_23 | RE | - |
testcase_24 | RE | - |
testcase_25 | RE | - |
testcase_26 | RE | - |
testcase_27 | RE | - |
testcase_28 | RE | - |
testcase_29 | RE | - |
testcase_30 | RE | - |
testcase_31 | RE | - |
testcase_32 | RE | - |
testcase_33 | RE | - |
testcase_34 | RE | - |
testcase_35 | RE | - |
testcase_36 | RE | - |
testcase_37 | RE | - |
testcase_38 | RE | - |
testcase_39 | RE | - |
testcase_40 | RE | - |
testcase_41 | RE | - |
testcase_42 | RE | - |
testcase_43 | RE | - |
testcase_44 | RE | - |
testcase_45 | RE | - |
testcase_46 | RE | - |
testcase_47 | RE | - |
testcase_48 | RE | - |
コンパイルメッセージ
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.Linq; using System.Text; class TEST{ static void Main(){ Sol mySol =new Sol(); mySol.Solve(); } } class Sol{ public void Solve(){ List<long> L = new List<long>(); int[] P = new int[1500000]; for(int i=2;i<1500000;i++){ if(P[i] == 0){ L.Add(i); for(int j=i+i;j<1500000;j += i) P[j] = 1; } } long mod = (long) 1e9+7; long[] ans = new long[Q]; for(int q=0;q<Q;q++){ long m = M[q]; long a = A[q]; long ret = 1; for(int i=1;i<=m;i++){ long p = L[i-1]; long pm = ModInv(p-1); long ret0 = p; ret0 *= (ModPow(p,i+a+1) + mod - 1); if(ret0 >= mod) ret0 %= mod; ret0 *= pm; if(ret0 >= mod) ret0 %= mod; ret0 += mod - (i+a+1) ; if(ret0 >= mod) ret0 -= mod; ret0 *= pm; if(ret0 >= mod) ret0 %= mod; ret *= ret0; if(ret >= mod) ret %= mod; } ans[q] = ret; } Console.WriteLine(String.Join("\n",ans)); } static long mod = (long) 1e9+7; static long ModInv(long x){ long a=0,b=0,c=0; if(x==0)return 0; ExtGCD(x,mod,ref a,ref b,ref c); if(c!=1)return 0; return (a+mod)%mod; } static long ModPow(long x,long k){ if(k == 0)return 1; if(x == 0)return 0; long ret = 1; long xx = x; while(k>0){ if((k&1)==1){ret *= xx; if(ret >= mod) ret %= mod;} xx *= xx; if(xx >= mod) xx %= mod; k>>=1; } return ret; } static void ExtGCD(long x,long y,ref long a,ref long b,ref long c){ long r0=x;long r1=y; long a0=1;long a1=0; long b0=0;long b1=1; long q1,r2,a2,b2; while(r1>0){ q1=r0/r1; r2=r0%r1; a2=a0-q1*a1; b2=b0-q1*b1; r0=r1;r1=r2; a0=a1;a1=a2; b0=b1;b1=b2; } c=r0; a=a0; b=b0; } int Q; int[] M,A; public Sol(){ Q = ri(); M = new int[Q]; A = new int[Q]; for(int i=0;i<Q;i++){ var d = ria(); M[i] = d[0]; A[i] = d[1]; } } static String rs(){return Console.ReadLine();} static int ri(){return int.Parse(Console.ReadLine());} static long rl(){return long.Parse(Console.ReadLine());} static double rd(){return double.Parse(Console.ReadLine());} static String[] rsa(char sep=' '){return Console.ReadLine().Split(sep);} static int[] ria(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>int.Parse(e));} static long[] rla(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>long.Parse(e));} static double[] rda(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>double.Parse(e));} }