#914386 (Fortran) No.2379 Burnside's Theorem

• 問題: No.2379 Burnside's Theorem
• ユーザー: osada-yum
• 提出日時: 2023-09-21 18:33:32
• 言語: Fortran (gFortran 14.2.0)
• 結果: AC
• 実行時間: 10 ms / 2,000 ms
• コード長: 13,295 bytes
• コンパイル時間: 1,683 ms
• コンパイル使用メモリ: 36,992 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-07-07 12:09:46
• 合計ジャッジ時間: 2,664 ms
• ジャッジサーバーID （参考情報）: judge1 / judge3

ファイルパターン	結果
sample	AC * 4
other	AC * 20

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
module unwrapped_vector_m
  use, intrinsic :: iso_fortran_env
  implicit none
  private
  public :: unwrapped_vector_int32
  type :: unwrapped_vector_int32
     private
     integer(int32), allocatable, public :: arr_(:)
     integer(int32) :: size_ = 0, capa_ = 0
   contains
     procedure, pass :: init      => init_unwrapped_vector_int32
     procedure, pass :: push_back_unwrapped_vector_int32, push_back_array_unwrapped_vector_int32
     generic         :: push_back => push_back_unwrapped_vector_int32, push_back_array_unwrapped_vector_int32
     procedure, pass :: pop_back  => pop_back_unwrapped_vector_int32
     procedure, pass :: back      => back_unwrapped_vector_int32
     procedure, pass :: size      => size_unwrapped_vector_int32
     procedure, pass :: resize    => resize_unwrapped_vector_int32
     procedure, pass :: lower_bound => lower_bound_unwrapped_vector_int32
  end type unwrapped_vector_int32
  interface unwrapped_vector_int32
     module procedure :: construct_unwrapped_vector_int32_by_size, &
          construct_unwrapped_vector_int32_by_arr, &
          construct_unwrapped_vector_int32_by_init_val
  end interface unwrapped_vector_int32
  public :: unwrapped_vector_int64
  type :: unwrapped_vector_int64
     private
     integer(int64), allocatable, public :: arr_(:)
     integer(int32) :: size_ = 0, capa_ = 0
   contains
     procedure, pass :: init      => init_unwrapped_vector_int64
     procedure, pass :: push_back_unwrapped_vector_int64, push_back_array_unwrapped_vector_int64
     generic         :: push_back => push_back_unwrapped_vector_int64, push_back_array_unwrapped_vector_int64
     procedure, pass :: pop_back  => pop_back_unwrapped_vector_int64
     procedure, pass :: back      => back_unwrapped_vector_int64
     procedure, pass :: size      => size_unwrapped_vector_int64
     procedure, pass :: resize    => resize_unwrapped_vector_int64
     procedure, pass :: lower_bound => lower_bound_unwrapped_vector_int64
  end type unwrapped_vector_int64
  interface unwrapped_vector_int64
     module procedure :: construct_unwrapped_vector_int64_by_size, &
          construct_unwrapped_vector_int64_by_arr, &
          construct_unwrapped_vector_int64_by_init_val
  end interface unwrapped_vector_int64
contains
  !> construct_unwrapped_vector_int32_by_size: Construct unwrapped_vector_int32 by the size, the initial values is unknown.
  impure function construct_unwrapped_vector_int32_by_size(size) result(res)
    type(unwrapped_vector_int32) :: res
    integer(int32), intent(in) :: size
    call res%init(size)
  end function construct_unwrapped_vector_int32_by_size
  !> construct_unwrapped_vector_int32_by_arr: Construct unwrapped_vector_int32 by the array of integer(int32).
  impure function construct_unwrapped_vector_int32_by_arr(arr) result(res)
    type(unwrapped_vector_int32) :: res
    integer(int32), intent(in) :: arr(:)
    integer(int32) :: n
    n = size(arr)
    call res%init(n)
    res%arr_(1:n) = arr(1:n)
  end function construct_unwrapped_vector_int32_by_arr
  !> construct_unwrapped_vector_int32_by_init_val: Construct unwrapped_vector_int32 by size and the initial values.
  impure function construct_unwrapped_vector_int32_by_init_val(size, val) result(res)
    type(unwrapped_vector_int32) :: res
    integer(int32), intent(in) :: size
    integer(int32), intent(in) :: val
    call res%init(size)
    res%arr_(1:size) = val
  end function construct_unwrapped_vector_int32_by_init_val
  !> init_unwrapped_vector_int32: Initialize the unwrapped_vector_int32 by size.
  subroutine init_unwrapped_vector_int32(this, n)
    class(unwrapped_vector_int32), intent(inout) :: this
    integer(int32), intent(in) :: n
    if (.not. allocated(this%arr_)) then
       allocate(this%arr_(n))
       this%size_ = n
       this%capa_ = n
    end if
  end subroutine init_unwrapped_vector_int32
  !> push_back_unwrapped_vector_int32: Insert value to the tail of elements of the unwrapped_vector_int32.
  subroutine push_back_unwrapped_vector_int32(this, val)
    class(unwrapped_vector_int32), intent(inout) :: this
    integer(int32), intent(in) :: val
    if (.not. allocated(this%arr_)) call this%resize(0)
    if (this%size_ == this%capa_) then
       call this%resize(2*this%capa_)
    end if
    this%size_ = this%size_ + 1
    this%arr_(this%size_) = val
  end subroutine push_back_unwrapped_vector_int32
  !> push_back_array_unwrapped_vector_int32: Insert elemeents of array to the tail of elements of the unwrapped_vector_int32.
  subroutine push_back_array_unwrapped_vector_int32(this, arr)
    class(unwrapped_vector_int32), intent(inout) :: this
    integer(int32), intent(in) :: arr(:)
    integer(int32) :: s
    s = size(arr)
    if (.not. allocated(this%arr_)) call this%init(s)
    if (this%size_ + s > this%capa_) then
       call this%resize(this%size_ + s)
    end if
    this%arr_(this%size_+1:this%size_+s) = arr(:)
    this%size_ = this%size_ + s
  end subroutine push_back_array_unwrapped_vector_int32
  !> pop_back_unwrapped_vector_int32: Delete the value in the end of arr_(:) of the unwrapped_vector_int32 and return it.
  integer(int32) function pop_back_unwrapped_vector_int32(this)
    class(unwrapped_vector_int32), intent(inout) :: this
    pop_back_unwrapped_vector_int32 = this%arr_(this%size_)
    this%size_ = this%size_ - 1
  end function pop_back_unwrapped_vector_int32
  !> back_unwrapped_vector_int32: Delete the value in the end of arr_(:) of the unwrapped_vector_int32 and return it.
  integer(int32) function back_unwrapped_vector_int32(this)
    class(unwrapped_vector_int32), intent(inout) :: this
    back_unwrapped_vector_int32 = this%arr_(this%size_)
  end function back_unwrapped_vector_int32
  !> size_vector_int32: Return current size of the unwrapped_vector_int32.
  pure integer(int32) function size_unwrapped_vector_int32(this)
    class(unwrapped_vector_int32), intent(in) :: this
    size_unwrapped_vector_int32 = this%size_
  end function size_unwrapped_vector_int32
  !> resize_unwrapped_vector_int32: Shrink or expand arr_(:) of the unwrapped_vector_int32.
  subroutine resize_unwrapped_vector_int32(this, resize)
    class(unwrapped_vector_int32), intent(inout) :: this
    integer(int32), intent(in) :: resize
    integer(int32), allocatable :: tmp(:)
    if (resize < 1) then
       this%size_ = 0
       allocate(tmp(1))
       call move_alloc(from = tmp, to = this%arr_)
       this%capa_ = 1
    else
       if (this%capa_ == resize) return
       allocate(tmp(resize))
       this%size_ = min(this%size_, resize)
       tmp(1:this%size_) = this%arr_(1:this%size_)
       call move_alloc(from = tmp, to = this%arr_)
       this%capa_ = resize
    end if
  end subroutine resize_unwrapped_vector_int32
  !> lower_bound_vector_int32: Return the minimum index that is higher than or equal to .
  integer(int32) function lower_bound_unwrapped_vector_int32(this, val)
    class(unwrapped_vector_int32), intent(in) :: this
    integer(int32), intent(in) :: val
    integer(int32) :: p, q, r
    p = 1
    r = this%size_
    if (this%arr_(r) < val) then
       lower_bound_unwrapped_vector_int32 = r + 1
       return
    end if
    do
       q = (p+r)/2
       if (p + 1 > r) exit
       if (this%arr_(q) >= val) then
          r = q
       else
          p = q+1
       end if
    end do
    lower_bound_unwrapped_vector_int32 = q
  end function lower_bound_unwrapped_vector_int32
  !> construct_unwrapped_vector_int64_by_size: Construct unwrapped_vector_int64 by the size, the initial values is unknown.
  impure function construct_unwrapped_vector_int64_by_size(size) result(res)
    type(unwrapped_vector_int64) :: res
    integer(int32), intent(in) :: size
    call res%init(size)
  end function construct_unwrapped_vector_int64_by_size
  !> construct_unwrapped_vector_int64_by_arr: Construct unwrapped_vector_int64 by the array of integer(int64).
  impure function construct_unwrapped_vector_int64_by_arr(arr) result(res)
    type(unwrapped_vector_int64) :: res
    integer(int64), intent(in) :: arr(:)
    integer(int32) :: n
    n = size(arr)
    call res%init(n)
    res%arr_(1:n) = arr(1:n)
  end function construct_unwrapped_vector_int64_by_arr
  !> construct_unwrapped_vector_int64_by_init_val: Construct unwrapped_vector_int64 by size and the initial values.
  impure function construct_unwrapped_vector_int64_by_init_val(size, val) result(res)
    type(unwrapped_vector_int64) :: res
    integer(int32), intent(in) :: size
    integer(int64), intent(in) :: val
    call res%init(size)
    res%arr_(1:size) = val
  end function construct_unwrapped_vector_int64_by_init_val
  !> init_unwrapped_vector_int64: Initialize the unwrapped_vector_int64 by size.
  subroutine init_unwrapped_vector_int64(this, n)
    class(unwrapped_vector_int64), intent(inout) :: this
    integer(int32), intent(in) :: n
    if (.not. allocated(this%arr_)) then
       allocate(this%arr_(n))
       this%size_ = n
       this%capa_ = n
    end if
  end subroutine init_unwrapped_vector_int64
  !> push_back_unwrapped_vector_int64: Insert value to the tail of elements of the unwrapped_vector_int64.
  subroutine push_back_unwrapped_vector_int64(this, val)
    class(unwrapped_vector_int64), intent(inout) :: this
    integer(int64), intent(in) :: val
    if (.not. allocated(this%arr_)) call this%resize(0)
    if (this%size_ == this%capa_) then
       call this%resize(2*this%capa_)
    end if
    this%size_ = this%size_ + 1
    this%arr_(this%size_) = val
  end subroutine push_back_unwrapped_vector_int64
  !> push_back_array_unwrapped_vector_int64: Insert elemeents of array to the tail of elements of the unwrapped_vector_int64.
  subroutine push_back_array_unwrapped_vector_int64(this, arr)
    class(unwrapped_vector_int64), intent(inout) :: this
    integer(int64), intent(in) :: arr(:)
    integer(int32) :: s
    s = size(arr)
    if (.not. allocated(this%arr_)) call this%init(s)
    if (this%size_ + s > this%capa_) then
       call this%resize(this%size_ + s)
    end if
    this%arr_(this%size_+1:this%size_+s) = arr(:)
    this%size_ = this%size_ + s
  end subroutine push_back_array_unwrapped_vector_int64
  !> pop_back_unwrapped_vector_int64: Delete the value in the end of arr_(:) of the unwrapped_vector_int64 and return it.
  integer(int64) function pop_back_unwrapped_vector_int64(this)
    class(unwrapped_vector_int64), intent(inout) :: this
    pop_back_unwrapped_vector_int64 = this%arr_(this%size_)
    this%size_ = this%size_ - 1
  end function pop_back_unwrapped_vector_int64
  !> back_unwrapped_vector_int64: Delete the value in the end of arr_(:) of the unwrapped_vector_int64 and return it.
  integer(int64) function back_unwrapped_vector_int64(this)
    class(unwrapped_vector_int64), intent(inout) :: this
    back_unwrapped_vector_int64 = this%arr_(this%size_)
  end function back_unwrapped_vector_int64
  !> size_vector_int64: Return current size of the unwrapped_vector_int64.
  pure integer(int32) function size_unwrapped_vector_int64(this)
    class(unwrapped_vector_int64), intent(in) :: this
    size_unwrapped_vector_int64 = this%size_
  end function size_unwrapped_vector_int64
  !> resize_unwrapped_vector_int64: Shrink or expand arr_(:) of the unwrapped_vector_int64.
  subroutine resize_unwrapped_vector_int64(this, resize)
    class(unwrapped_vector_int64), intent(inout) :: this
    integer(int32), intent(in) :: resize
    integer(int64), allocatable :: tmp(:)
    if (resize < 1) then
       this%size_ = 0
       allocate(tmp(1))
       call move_alloc(from = tmp, to = this%arr_)
       this%capa_ = 1
    else
       if (this%capa_ == resize) return
       allocate(tmp(resize))
       this%size_ = min(this%size_, resize)
       tmp(1:this%size_) = this%arr_(1:this%size_)
       call move_alloc(from = tmp, to = this%arr_)
       this%capa_ = resize
    end if
  end subroutine resize_unwrapped_vector_int64
  !> lower_bound_vector_int64: Return the minimum index that is higher than or equal to .
  integer(int32) function lower_bound_unwrapped_vector_int64(this, val)
    class(unwrapped_vector_int64), intent(in) :: this
    integer(int64), intent(in) :: val
    integer(int32) :: p, q, r
    p = 1
    r = this%size_
    if (this%arr_(r) < val) then
       lower_bound_unwrapped_vector_int64 = r + 1
       return
    end if
    do
       q = (p+r)/2
       if (p + 1 > r) exit
       if (this%arr_(q) >= val) then
          r = q
       else
          p = q+1
       end if
    end do
    lower_bound_unwrapped_vector_int64 = q
  end function lower_bound_unwrapped_vector_int64
end module unwrapped_vector_m
program yukicoder_2379
  use, intrinsic :: iso_fortran_env
  use unwrapped_vector_m, only: vec_i64 => unwrapped_vector_int64
  implicit none
  integer(int32), parameter :: max_factor = 1000
  integer(int64) :: n_orig, n
  type(vec_i64) :: factors
  integer(int64) :: i
  read(input_unit, *) n_orig
  n = n_orig
  i = 2_int64
  call factors%push_back(1_int64)
  do while (i * i <= n)
     do while (mod(n, i) == 0)
        n = n / i
        if (factors%back() /= i) call factors%push_back(i)
     end do
     i = i + 1
  end do
  if (n > 1 .and. factors%back() /= n) &
       call factors%push_back(n)
  write(output_unit, '(a)') trim(merge("Yes", "No ", factors%size() <= 3))
end program yukicoder_2379
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX