結果

問題 No.28 末尾最適化
ユーザー 37zigen37zigen
提出日時 2018-04-03 18:23:45
言語 Fortran
(gFortran 13.2.0)
結果
WA  
実行時間 -
コード長 2,127 bytes
コンパイル時間 137 ms
コンパイル使用メモリ 27,700 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-08 15:30:48
合計ジャッジ時間 966 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

module m
    implicit none
    integer(kind=8)::p=100000009

contains
    subroutine solve(seed,n,k,b)
        implicit none
        integer(kind=8)::seed,n,k,b,x(0:10000),div(3),pow(3),cnt(0:70)
        integer(kind=8)::ans
        integer(kind=8)::i,j,r,tmp,tmp1,tmp2,tmp3,gen
        ans=1000000
        x(0)=seed
        do i=0,n-1
            x(i+1)=next(x(i))
        end do

        call factor(b,div,gen,pow)

        do i=1,gen-1
            do j=1,size(cnt)
                cnt(j-1)=0
            end do
            do j=0,n
                tmp=x(j)
                r=0
                do while(tmp>1.and.mod(tmp,div(i))==0)
                    tmp=tmp/div(i)
                    r=r+1
                end do
                cnt(r)=cnt(r)+1
            end do
            r=k
            tmp=0
            do j=0,size(cnt)-1
                if(r-cnt(j)<=0)then
                    tmp=tmp+r*j
                    r=0
                    exit
                else
                    tmp=tmp+cnt(j)*j
                    r=r-cnt(j)
                end if
            end do
            ans=min(ans,tmp/pow(i))
        end do

        print*,ans

    end subroutine

    subroutine factor(n,div,gen,pow)
        integer(kind=8),intent(in)::n
        integer(kind=8)::gen,tmp,div(*),pow(*),r,i,j
        gen=1
        tmp=n
        do i=2,tmp
            r=0
            do while(mod(tmp,i)==0)
                tmp=tmp/i
                r=r+1
            end do
            if(r>0)then
                div(gen)=i
                pow(gen)=r
                gen=gen+1
            end if
            if(i*i>=tmp)exit
        end do
        if(tmp>1)then
            div(gen)=tmp
            pow(gen)=1
            gen=gen+1
        end if
    end subroutine

    integer(kind=8) function next(x)
        integer(kind=8)::x
        next=1+mod(mod(x*x,p)+mod(x*12345,p),p)
    end function

end module


program main
    use m
    implicit none
    integer(kind=8)::q,seed,n,k,b
    integer::i,j,x,y,z,r
    read*,q
    print*,q
    do i=1,q
        read(*,*)seed,n,k,b
        call solve(seed,n,k,b)
    end do

end program
0