結果

問題 No.186 中華風 (Easy)
ユーザー 👑 naipianaipia
提出日時 2020-09-26 00:38:58
言語 Go
(1.22.1)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,903 bytes
コンパイル時間 11,598 ms
コンパイル使用メモリ 214,660 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-09-27 01:03:40
合計ジャッジ時間 12,292 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 1 ms
4,380 KB
testcase_05 AC 1 ms
4,380 KB
testcase_06 AC 1 ms
4,380 KB
testcase_07 AC 1 ms
4,380 KB
testcase_08 AC 1 ms
4,380 KB
testcase_09 AC 2 ms
4,380 KB
testcase_10 AC 2 ms
4,376 KB
testcase_11 AC 1 ms
4,380 KB
testcase_12 AC 1 ms
4,376 KB
testcase_13 AC 1 ms
4,380 KB
testcase_14 AC 1 ms
4,380 KB
testcase_15 AC 1 ms
4,376 KB
testcase_16 AC 1 ms
4,380 KB
testcase_17 AC 1 ms
4,380 KB
testcase_18 AC 1 ms
4,380 KB
testcase_19 AC 1 ms
4,380 KB
testcase_20 AC 1 ms
4,380 KB
testcase_21 AC 1 ms
4,380 KB
testcase_22 AC 1 ms
4,384 KB
権限があれば一括ダウンロードができます

ソースコード

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 := 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
}
0