結果

問題 No.882 約数倍数
ユーザー sansaquasansaqua
提出日時 2019-09-13 21:21:52
言語 Common Lisp
(sbcl 2.3.8)
結果
AC  
実行時間 11 ms / 500 ms
コード長 6,523 bytes
コンパイル時間 1,253 ms
コンパイル使用メモリ 41,772 KB
実行使用メモリ 30,784 KB
最終ジャッジ日時 2024-07-04 03:54:43
合計ジャッジ時間 1,981 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 11 ms
26,664 KB
testcase_01 AC 11 ms
30,780 KB
testcase_02 AC 11 ms
26,668 KB
testcase_03 AC 11 ms
30,632 KB
testcase_04 AC 10 ms
26,664 KB
testcase_05 AC 11 ms
28,616 KB
testcase_06 AC 10 ms
28,748 KB
testcase_07 AC 11 ms
30,648 KB
testcase_08 AC 11 ms
30,784 KB
testcase_09 AC 10 ms
26,664 KB
testcase_10 AC 11 ms
30,776 KB
testcase_11 AC 10 ms
26,664 KB
testcase_12 AC 11 ms
26,664 KB
testcase_13 AC 10 ms
26,664 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
; compiling file "/home/judge/data/code/Main.lisp" (written 04 JUL 2024 03:54:41 AM):

; file: /home/judge/data/code/Main.lisp
; in: DEFUN MAKE-DIVISORS-TABLE
;     (MAKE-ARRAY SUP :ELEMENT-TYPE 'LIST)
; 
; caught STYLE-WARNING:
;   The default initial element 0 is not a LIST.
;   See also:
;     The ANSI Standard, Function MAKE-ARRAY
;     The ANSI Standard, Function UPGRADED-ARRAY-ELEMENT-TYPE
; 
; caught STYLE-WARNING:
;   The default initial element 0 is not a LIST.
;   See also:
;     The ANSI Standard, Function MAKE-ARRAY
;     The ANSI Standard, Function UPGRADED-ARRAY-ELEMENT-TYPE
; 
; compilation unit finished
;   caught 2 STYLE-WARNING conditions


; wrote /home/judge/data/code/Main.fasl
; compilation finished in 0:00:00.054

ソースコード

diff # 

;; -*- coding: utf-8 -*-
(eval-when (:compile-toplevel :load-toplevel :execute)
  (sb-int:defconstant-eqx OPT
    #+swank '(optimize (speed 3) (safety 2))
    #-swank '(optimize (speed 3) (safety 0) (debug 0))
    #'equal)
  #+swank (ql:quickload '(:cl-debug-print :fiveam) :silent t)
  #-swank (set-dispatch-macro-character
           #\# #\> (lambda (s c p) (declare (ignore c p)) (read s nil nil t))))
#+swank (cl-syntax:use-syntax cl-debug-print:debug-print-syntax)
#-swank (disable-debugger) ; for CS Academy

;; BEGIN_INSERTED_CONTENTS
(declaim (ftype (function * (values (vector (integer 0 #.most-positive-fixnum)) &optional))
                enum-divisors))
(defun enum-divisors (x)
  "Enumerates all the divisors of X in O(sqrt(X)). Note that the resultant
vector is NOT sorted."
  (declare (optimize (speed 3))
           ((integer 0 #.most-positive-fixnum) x))
  (let* ((sqrt (isqrt x))
         (res (make-array (isqrt sqrt) ; FIXME: sets the initial size to x^1/4
                          :element-type '(integer 0 #.most-positive-fixnum)
                          :fill-pointer 0)))
    (loop for i from 1 to sqrt
          do (multiple-value-bind (quot rem) (floor x i)
               (when (zerop rem)
                 (vector-push-extend i res)
                 (unless (= i quot)
                   (vector-push-extend quot res)))))
    res))

;; Below is the variant that returns a sorted list.
;; (defun enum-divisors (n)
;;   "Returns the increasing list of all the divisors of N."
;;   (declare (optimize (speed 3))
;;            ((integer 1 #.most-positive-fixnum) n))
;;   (if (= n 1)
;;       (list 1)
;;       (let* ((sqrt (isqrt n))
;;              (result (list 1)))
;;         (labels ((%enum (i first-half second-half)
;;                    (declare ((integer 1 #.most-positive-fixnum) i))
;;                    (cond ((or (< i sqrt)
;;                               (and (= i sqrt) (/= (* sqrt sqrt) n)))
;;                           (multiple-value-bind (quot rem) (floor n i)
;;                             (if (zerop rem)
;;                                 (progn
;;                                   (setf (cdr first-half) (list i))
;;                                   (setf second-half (cons quot second-half))
;;                                   (%enum (1+ i) (cdr first-half) second-half))
;;                                 (%enum (1+ i) first-half second-half))))
;;                          ((= i sqrt) ; N is a square number here
;;                           (setf (cdr first-half) (cons i second-half)))
;;                          (t ; (> i sqrt)
;;                           (setf (cdr first-half) second-half)))))
;;           (%enum 2 result (list n))
;;           result))))

(defun make-divisors-table (sup)
  "Returns a vector of length SUP whose each cell, vector[INDEX], is the
increasing list of every divisor of INDEX. Note that vector[0] = NIL."
  (declare ((integer 0 #.most-positive-fixnum) sup))
  (let ((result (make-array sup :element-type 'list))
        (tails (make-array sup :element-type 'list))) ; preserves the last cons
    (declare (optimize (speed 3) (safety 0)))
    (loop for i from 1 below sup
          for cell = (list 1)
          do (setf (aref result i) cell
                   (aref tails i) cell))
    (when (>= sup 1)
      (setf (aref result 0) nil))
    (loop for divisor from 2 below sup
          do (loop for number from divisor below sup by divisor
                   do (setf (cdr (aref tails number)) (list divisor))
                      (setf (aref tails number) (cdr (aref tails number)))))
    result))

(defmacro dbg (&rest forms)
  #+swank
  (if (= (length forms) 1)
      `(format *error-output* "~A => ~A~%" ',(car forms) ,(car forms))
      `(format *error-output* "~A => ~A~%" ',forms `(,,@forms)))
  #-swank (declare (ignore forms)))

(defmacro define-int-types (&rest bits)
  `(progn
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "UINT~A" b)) () '(unsigned-byte ,b))) bits)
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "INT~A" b)) () '(signed-byte ,b))) bits)))
(define-int-types 2 4 7 8 15 16 31 32 62 63 64)

(declaim (inline println))
(defun println (obj &optional (stream *standard-output*))
  (let ((*read-default-float-format* 'double-float))
    (prog1 (princ obj stream) (terpri stream))))

(defconstant +mod+ 1000000007)

;;;
;;; Body
;;;

(defun main ()
  (let* ((a (read))
         (b (read))
         (divisors (enum-divisors a)))
    (sb-int:dovector (x divisors)
      (when (zerop (mod x b))
        (write-line "YES")
        (return-from main)))
    (write-line "NO")))

#-swank (main)

;;;
;;; Test and benchmark
;;;

#+swank
(defun io-equal (in-string out-string &key (function #'main) (test #'equal))
  "Passes IN-STRING to *STANDARD-INPUT*, executes FUNCTION, and returns true if
the string output to *STANDARD-OUTPUT* is equal to OUT-STRING."
  (labels ((ensure-last-lf (s)
             (if (eql (uiop:last-char s) #\Linefeed)
                 s
                 (uiop:strcat s uiop:+lf+))))
    (funcall test
             (ensure-last-lf out-string)
             (with-output-to-string (out)
               (let ((*standard-output* out))
                 (with-input-from-string (*standard-input* (ensure-last-lf in-string))
                   (funcall function)))))))

#+swank
(defun get-clipbrd ()
  (with-output-to-string (out)
    (run-program "C:/msys64/usr/bin/cat.exe" '("/dev/clipboard") :output out)))

#+swank (defparameter *this-pathname* (uiop:current-lisp-file-pathname))
#+swank (defparameter *dat-pathname* (uiop:merge-pathnames* "test.dat" *this-pathname*))

#+swank
(defun run (&optional thing (out *standard-output*))
  "THING := null | string | symbol | pathname

null: run #'MAIN using the text on clipboard as input.
string: run #'MAIN using the string as input.
symbol: alias of FIVEAM:RUN!.
pathname: run #'MAIN using the text file as input."
  (let ((*standard-output* out))
    (etypecase thing
      (null
       (with-input-from-string (*standard-input* (delete #\Return (get-clipbrd)))
         (main)))
      (string
       (with-input-from-string (*standard-input* (delete #\Return thing))
         (main)))
      (symbol (5am:run! thing))
      (pathname
       (with-open-file (*standard-input* thing)
         (main))))))

#+swank
(defun gen-dat ()
  (uiop:with-output-file (out *dat-pathname* :if-exists :supersede)
    (format out "")))

#+swank
(defun bench (&optional (out (make-broadcast-stream)))
  (time (run *dat-pathname* out)))
0