結果

問題 No.2440 Accuracy of Integer Division Approximate Functions
ユーザー 👑 Mizar
提出日時 2023-08-21 08:59:59
言語 Go
(1.23.4)
結果
AC  
実行時間 95 ms / 2,000 ms
コード長 1,591 bytes
コンパイル時間 16,673 ms
コンパイル使用メモリ 222,636 KB
実行使用メモリ 6,528 KB
最終ジャッジ日時 2024-12-23 06:22:25
合計ジャッジ時間 17,342 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

import (
	"bufio"
	"fmt"
	"math/big"
	"os"
)

// calc sum_{i=0}^{n-1} floor((ai + b) / m)
func floor_sum_unsigned(ni *big.Int, mi *big.Int, ai *big.Int, bi *big.Int) big.Int {
	n := new(big.Int).Set(ni)
	m := new(big.Int).Set(mi)
	a := new(big.Int).Set(ai)
	b := new(big.Int).Set(bi)
	ans := big.NewInt(0)
	for true {
		if a.Cmp(m) >= 0 {
			var am, t big.Int
			am.DivMod(a, m, a)
			t.Sub(n, big.NewInt(1)).Mul(&t, n).Rsh(&t, 1).Mul(&t, &am)
			ans.Add(ans, &t)
		}
		if b.Cmp(m) >= 0 {
			var bm, t big.Int
			bm.DivMod(b, m, b)
			t.Mul(n, &bm)
			ans.Add(ans, &t)
		}
		var y_max big.Int
		y_max.Mul(a, n)
		y_max.Add(&y_max, b)
		if y_max.Cmp(m) == -1 {
			break
		}
		n.DivMod(&y_max, m, b)
		m, a = a, m
	}
	return *ans
}

func solve(n *big.Int, d *big.Int, m *big.Int, s uint) big.Int {
	var pow2s, dm big.Int
	a := new(big.Int).Set(n)
	pow2s.Lsh(big.NewInt(1), s)
	dm.Mul(new(big.Int).Set(d), new(big.Int).Set(m))
	if pow2s.Cmp(&dm) != 0 {
		var aa, p2dm, a1 big.Int
		p2dm.Sub(&dm, &pow2s).Abs(&p2dm)
		aa.Mul(d, &pow2s).Div(&aa, &p2dm)
		if a.Cmp(&aa) == 1 {
			a.Set(&aa)
		}
		a1.Add(a, big.NewInt(1))
		t := floor_sum_unsigned(&a1, &pow2s, m, big.NewInt(0))
		t2 := floor_sum_unsigned(&a1, d, big.NewInt(1), big.NewInt(0))
		t.Sub(&t, &t2).Abs(&t)
		a.Sub(a, &t)
	}
	return *a
}

func main() {
	r := bufio.NewReader(os.Stdin)
	w := bufio.NewWriter(os.Stdout)
	defer w.Flush()

	var q int
	fmt.Fscan(r, &q)

	for i := 0; i < q; i++ {
		var n, d, m big.Int
		var s uint
		fmt.Fscan(r, &n, &d, &m, &s)
		c := solve(&n, &d, &m, s)
		fmt.Fprintln(w, c.String())
	}
}
0