#558713 (Go) No.186 中華風 (Easy)

• 問題: No.186 中華風 (Easy)
• ユーザー: naipia
• 提出日時: 2020-09-26 00:38:58
• 言語: Go (1.22.1)
• 結果: AC
• 実行時間: 2 ms / 2,000 ms
• コード長: 1,903 bytes
• コンパイル時間: 11,529 ms
• コンパイル使用メモリ: 224,708 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-07-19 18:43:05
• 合計ジャッジ時間: 12,339 ms
• ジャッジサーバーID （参考情報）: judge1 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	1 ms; 5,376 KB
testcase_02	AC	1 ms; 5,376 KB
testcase_03	AC	1 ms; 5,376 KB
testcase_04	AC	1 ms; 5,376 KB
testcase_05	AC	2 ms; 5,376 KB
testcase_06	AC	1 ms; 5,376 KB
testcase_07	AC	1 ms; 5,376 KB
testcase_08	AC	1 ms; 5,376 KB
testcase_09	AC	1 ms; 5,376 KB
testcase_10	AC	1 ms; 5,376 KB
testcase_11	AC	1 ms; 5,376 KB
testcase_12	AC	1 ms; 5,376 KB
testcase_13	AC	1 ms; 5,376 KB
testcase_14	AC	1 ms; 5,376 KB
testcase_15	AC	1 ms; 5,376 KB
testcase_16	AC	1 ms; 5,376 KB
testcase_17	AC	1 ms; 5,376 KB
testcase_18	AC	1 ms; 5,376 KB
testcase_19	AC	1 ms; 5,376 KB
testcase_20	AC	1 ms; 5,376 KB
testcase_21	AC	1 ms; 5,376 KB
testcase_22	AC	1 ms; 5,376 KB

ソースコード

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 := 3
	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 {
		if r == 0 {
			fmt.Fprintln(wr, m)
		} else {
			fmt.Fprintln(wr, r)
		}
	}
}

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++ {
		r1, m1 := r[i], m[i]
		if m0 < m1 {
			r0, r1 = r1, r0
			m0, m1 = m1, m0
		}

		if m0%m1 == 0 {
			if r0%m1 != r1 {
				return 0, 0
			}
			continue
		}

		g, im := invGcd(m0, m1)
		if (r1-r0)%g != 0 {
			return 0, 0
		}

		u := m1 / g
		x := (r1 - r0) / g % u * im % u
		r0 += m0 * x
		m0 *= u
	}

	return (r0%m0 + m0) % m0, m0
}