結果

問題 No.308 素数は通れません
ユーザー yosupot
提出日時 2015-12-01 23:21:40
言語 Go
(1.23.4)
結果
AC  
実行時間 439 ms / 1,000 ms
コード長 2,409 bytes
コンパイル時間 17,732 ms
コンパイル使用メモリ 237,736 KB
実行使用メモリ 7,248 KB
最終ジャッジ日時 2024-11-27 18:23:30
合計ジャッジ時間 23,735 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 107
権限があれば一括ダウンロードができます

ソースコード

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

package main
import (
    "fmt"
    "math/big"
    "os"
)
type UnionFind struct {
    n  int
    ig []int
    gi [][]int
}
func MakeUF(n int) *UnionFind {
    uf := new(UnionFind)
    uf.n = n
    uf.ig = make([]int, n)
    uf.gi = make([][]int, n)
    for i := 0; i < n; i++ {
        uf.ig[i] = i
        uf.gi[i] = []int{i}
    }
    return uf
}
func (uf *UnionFind) merge(a, b int) {
    a = uf.ig[a]
    b = uf.ig[b]
    if a == b {
        return
    }
    if len(uf.gi[a]) < len(uf.gi[b]) {
        tmp := a
        a = b
        b = tmp
    }
    for _, c := range uf.gi[b] {
        uf.ig[c] = a
    }
    uf.gi[a] = append(uf.gi[a], uf.gi[b]...)
}
func (uf *UnionFind) same(a, b int) bool {
    return uf.ig[a] == uf.ig[b]
}
const PS = 50000
var pr [PS]bool
func init() {
    for i := 2; i < PS; i++ {
        pr[i] = true
    }
    for i := 2; i < PS; i++ {
        if pr[i] == false {
            continue
        }
        for j := 2 * i; j < PS; j += i {
            pr[j] = false
        }
    }
}
func solve1(n int) int {
    for i := 2; i <= n; i++ {
        uf := MakeUF(n + 1)
        for j := 1; j <= n; j++ {
            if j%i != 1 {
                if !pr[j] && !pr[j-1] {
                    uf.merge(j, j-1)
                }
            }
            if i < j {
                if !pr[j] && !pr[j-i] {
                    uf.merge(j, j-i)
                }
            }
        }
        if uf.same(1, n) {
            return i
        }
    }
    os.Exit(1)
    return -1
}
func solve2(n *big.Int) int {
    for i := 2; i < 1000; i++ {
        const B = 9000
        {
            uf := MakeUF(B + 1)
            for j := 1; j <= B; j++ {
                if j%i != 1 {
                    if !pr[j] && !pr[j-1] {
                        uf.merge(j, j-1)
                    }
                }
                if i < j {
                    if !pr[j] && !pr[j-i] {
                        uf.merge(j, j-i)
                    }
                }
            }
            if !uf.same(1, B/i*i) {
                continue
            }
        }
        {
            uf := MakeUF(B + 1)
            ii := big.NewInt(int64(i))
            bpr := make([]bool, B+1)
            for jj := 0; jj <= B; jj++ {
                j := new(big.Int)
                j.Set(n).Sub(j, big.NewInt(int64(B-jj)))
                bpr[jj] = j.ProbablyPrime(100)
            }
            for jj := 1; jj <= B; jj++ {
                j := new(big.Int)
                j.Set(n).Sub(j, big.NewInt(int64(B-jj)))
                k := new(big.Int)
                k.Set(j)
                if k.Mod(k, ii).Cmp(big.NewInt(1)) != 0 {
                    if !bpr[jj] && !bpr[jj-1] {
                        uf.merge(jj, jj-1)
                    }
                }
                if i <= jj {
                    if !bpr[jj] && !bpr[jj-i] {
                        uf.merge(jj, jj-i)
                    }
                }
            }
            nn := new(big.Int)
            nn.Set(n)
            if uf.same(B-int(nn.Mod(nn, big.NewInt(int64(i))).Int64()), B) {
                return i
            }
        }
    }
    os.Exit(1)
    return -1
}
func main() {
    b := new(big.Int)
    fmt.Scan(b)
    if b.Cmp(big.NewInt(20000)) == -1 {
        fmt.Println(solve1(int(b.Int64())))
    } else {
        fmt.Println(solve2(b))
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0