結果

問題 No.129 お年玉(2)
ユーザー yukirin
提出日時 2016-02-26 17:34:48
言語 Go
(1.23.4)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 1,391 bytes
コンパイル時間 10,485 ms
コンパイル使用メモリ 220,472 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-28 00:16:50
合計ジャッジ時間 11,639 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 46
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

package main
import (
    "bufio"
    "fmt"
    "math"
    "os"
    "strconv"
)
var sc = bufio.NewScanner(os.Stdin)
var rdr = bufio.NewReaderSize(os.Stdin, 1000000)
func main() {
    sc.Split(bufio.ScanWords)
    n, m := nextInt(), nextInt()
    n -= n % 1000
    mod := (n/1000 - n/(1000*m)*m)
    fmt.Println(ncr(uint64(m), uint64(mod), 1000000000))
}
func ncr(n, r, mod uint64) uint64 {
    if n < 0 || r < 0 || r > n {
        return 0
    }
    if r > n/2 {
        r = n - r
    }
    a := make([]uint64, n)
    for i := range a {
        a[i] = n - uint64(i)
    }
    ps := eratosthenes(int(r))
    for _, p := range ps {
        for q := uint64(p); q <= r; q *= uint64(p) {
            m := n % q
            for i, j := m, uint64(0); j < r/q; i, j = i+q, j+1 {
                a[i] /= uint64(p)
            }
        }
    }
    mul := uint64(1)
    for i := uint64(0); i < r; i++ {
        mul = mul * a[i] % mod
    }
    return mul
}
func nextLine() string {
    sc.Scan()
    return sc.Text()
}
func nextInt() int {
    i, _ := strconv.Atoi(nextLine())
    return i
}
func eratosthenes(n int) []int {
    if n < 2 {
        return []int{}
    }
    r := int(math.Floor(math.Sqrt(float64(n))))
    list := make([]bool, n+1)
    list[0], list[1] = true, true
    for i := 2; i <= r; i++ {
        if !list[i] {
            for j := i * i; j <= n; j += i {
                list[j] = true
            }
        }
    }
    l := n / int(math.Ceil(math.Log(float64(n))))
    primes := make([]int, 0, l)
    for i, v := range list {
        if v {
            continue
        }
        primes = append(primes, i)
    }
    return primes
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0