結果

問題 No.187 中華風 (Hard)
コンテスト
ユーザー naipia
提出日時 2020-09-26 00:04:27
言語 Go
(1.23.4)
結果
WA  
実行時間 -
コード長 1,748 bytes
コンパイル時間 15,169 ms
コンパイル使用メモリ 232,500 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-28 08:26:13
合計ジャッジ時間 15,496 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10 WA * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc, wr = bufio.NewScanner(os.Stdin), bufio.NewWriter(os.Stdout)

func scanString() string   { sc.Scan(); return sc.Text() }
func scanRunes() []rune    { return []rune(scanString()) }
func scanInt() int         { a, _ := strconv.Atoi(scanString()); return a }
func scanInt64() int64     { a, _ := strconv.ParseInt(scanString(), 10, 64); return a }
func scanFloat64() float64 { a, _ := strconv.ParseFloat(scanString(), 64); return a }

func scanInts(n int) []int {
	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i] = scanInt()
	}
	return a
}

func debug(a ...interface{}) {
	if os.Getenv("ONLINE_JUDGE") == "false" {
		fmt.Fprintln(os.Stderr, a...)
	}
}

func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}
func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

//•*¨*•.¸¸♪main•*¨*•.¸¸♪(　-ω-)ノ　(　・ω・)
func main() {
	defer wr.Flush()
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 1001), 1001001)

	n := scanInt()
	x, y := make([]int, n), make([]int, n)
	for i := 0; i < n; i++ {
		x[i], y[i] = scanInt(), scanInt()
	}
	r, m := crt(x, y)
	if m == 0 {
		fmt.Fprintln(wr, -1)
	} else {
		fmt.Fprintln(wr, r%mod)
	}

}

const mod = 1000000007

func crt(r []int, m []int) (int, int) {
	r0, m0 := 0, 1

	invGcd := func(a, p int) (int, int) {
		x, u := 1, 0
		for p != 0 {
			t := a / p
			a, p = p, a-t*p
			x, u = u, x-t*u
		}
		return a, x
	}

	for i := 0; i < len(r); i++ {
		g, im := invGcd(m0, m[i])
		if (r[i]-r0)%g != 0 {
			return 0, 0
		}
		x := (r[i] - r0) / g * im % (m[i] / g)
		r0 += m0 * x
		m0 *= m[i] / g
		if r0 < 0 {
			r0 += m0
		}
	}

	return r0, m0
}
0