結果
問題 | No.3030 ミラー・ラビン素数判定法のテスト |
ユーザー | 37zigen |
提出日時 | 2018-04-09 00:59:35 |
言語 | Fortran (gFortran 13.2.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,666 bytes |
コンパイル時間 | 194 ms |
コンパイル使用メモリ | 33,144 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-11-18 16:19:18 |
合計ジャッジ時間 | 29,358 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,816 KB |
testcase_01 | AC | 1 ms
6,816 KB |
testcase_02 | AC | 1 ms
6,816 KB |
testcase_03 | AC | 2 ms
6,820 KB |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | TLE | - |
ソースコード
module mdl contains function mul_mod(a,b,m)result(ret) implicit none integer(8),value::a,b,m integer(8)::ret,tmp a=mod(a,m) b=mod(b,m) ret=0 do while(b>1) if(mod(b,2)==0)then tmp=a if(tmp>=m-a)tmp=tmp-m a=mod(a+tmp,m) b=b/2 else if(ret>=m-a)ret=ret-m ret=mod(ret+a,m) b=b-1 end if end do if(ret>=m-a)ret=ret-m ret=mod(ret+a,m) end function integer(8) function pow(a,n,p) implicit none integer(8),value::a,n,p a=mod(a,p) pow=1 do while(n>0) if(mod(n,2)==1)pow=mul_mod(pow,a,p) n=n/2 a=mul_mod(a,a,p) end do end function logical function isPrime(a) integer(8)::i,j,k,x,tmp integer(8),value::a logical::flag isPrime=.true. do i=12,min(a-1,20) tmp=pow(i,a-1,a) isPrime=isPrime.and.tmp==1 if(.not.isPrime)return end do if(a<10000)then do i=2,a if(i*i>=a)exit isPrime=isPrime.and.mod(a,i)/=0 if(isPrime)return end do end if end function end module program main use mdl implicit none integer::n integer(8)::i,j,k integer(8),allocatable::x(:) read*,n allocate(x(n)) do i=1,n read*,x(i) if(isPrime(x(i)))then print*,x(i),1 else print*,x(i),0 end if end do end program