結果
問題 | No.3030 ミラー・ラビン素数判定法のテスト |
ユーザー | 37zigen |
提出日時 | 2018-04-09 02:16:22 |
言語 | Fortran (gFortran 13.2.0) |
結果 |
AC
|
実行時間 | 3,758 ms / 9,973 ms |
コード長 | 1,898 bytes |
コンパイル時間 | 1,638 ms |
コンパイル使用メモリ | 33,408 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-16 23:08:10 |
合計ジャッジ時間 | 11,013 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,248 KB |
testcase_02 | AC | 1 ms
5,248 KB |
testcase_03 | AC | 1 ms
5,248 KB |
testcase_04 | AC | 1,937 ms
5,248 KB |
testcase_05 | AC | 1,824 ms
5,248 KB |
testcase_06 | AC | 462 ms
5,248 KB |
testcase_07 | AC | 475 ms
5,248 KB |
testcase_08 | AC | 457 ms
5,248 KB |
testcase_09 | AC | 3,758 ms
5,248 KB |
ソースコード
module mdl integer(8)::prime(12)=[2,3,5,7,11,13,17,19,23,29,31,37] 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=a+tmp b=b/2 else if(ret>=m-a)ret=ret-m ret=ret+a b=b-1 end if end do if(ret>=m-a)ret=ret-m ret=ret+a 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)::q,i,j,k,x,y,tmp integer(8),value::a logical::flag isPrime=.true. if(a==2)return if(a==1.or.mod(a,2)==0)then isPrime=.false. return end if q=a-1 do while(mod(q,2)==0) q=q/2 end do do i=1,size(prime) x=pow(prime(i),q,a) y=q do while(y/=a-1.and.x/=1.and.x/=a-1) y=y*2 x=mul_mod(x,x,a) end do if(x/=a-1.and.mod(y,2)==0)then isPrime=.false. return end if end do 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