結果
問題 | No.886 Direct |
ユーザー | 草苺奶昔 |
提出日時 | 2023-02-24 18:33:53 |
言語 | Go (1.22.1) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,185 bytes |
コンパイル時間 | 13,921 ms |
コンパイル使用メモリ | 217,972 KB |
実行使用メモリ | 143,264 KB |
最終ジャッジ日時 | 2024-09-13 03:00:31 |
合計ジャッジ時間 | 14,806 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 1 ms
6,812 KB |
testcase_02 | WA | - |
testcase_03 | RE | - |
testcase_04 | AC | 2 ms
6,944 KB |
testcase_05 | AC | 2 ms
6,940 KB |
testcase_06 | AC | 1 ms
6,940 KB |
testcase_07 | RE | - |
testcase_08 | WA | - |
testcase_09 | RE | - |
testcase_10 | RE | - |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | RE | - |
testcase_14 | RE | - |
testcase_15 | RE | - |
testcase_16 | WA | - |
testcase_17 | RE | - |
testcase_18 | WA | - |
testcase_19 | RE | - |
testcase_20 | RE | - |
testcase_21 | WA | - |
testcase_22 | RE | - |
testcase_23 | RE | - |
testcase_24 | WA | - |
testcase_25 | WA | - |
testcase_26 | RE | - |
testcase_27 | WA | - |
testcase_28 | RE | - |
testcase_29 | RE | - |
testcase_30 | AC | 20 ms
50,816 KB |
testcase_31 | WA | - |
testcase_32 | RE | - |
testcase_33 | WA | - |
testcase_34 | RE | - |
testcase_35 | RE | - |
ソースコード
package main import ( "bufio" "fmt" "os" ) func main() { in := bufio.NewReader(os.Stdin) out := bufio.NewWriter(os.Stdout) defer out.Flush() var ROW, COL int fmt.Fscan(in, &ROW, &COL) res := ROW*(COL-1) + COL*(ROW-1) // 原来相邻的线段数 A, B := make([]int, ROW+1), make([]int, COL+1) for i := 0; i < ROW; i++ { A[i] = ROW - i } for i := 0; i < COL; i++ { B[i] = COL - i } C := GcdConvolution(A, B) fmt.Fprintln(out, (res+C[1]*2)%MOD) // pair of gcd(row,col)=1 } const MOD int = 1e9 + 7 // c[k] = ∑a[i]*b[j] mod MOD, gcd(i,j)=k func GcdConvolution(nums1, nums2 []int) []int { n := len(nums1) pf := make([]int, n+1) copy1, copy2 := append([]int{0}, nums1...), append([]int{0}, nums2...) for i := 2; i < n+1; i++ { if pf[i] == 0 { for j := n / i; j > 0; j-- { pf[j*i] = 1 copy1[j] = (copy1[j] + copy1[j*i]) % MOD copy2[j] = (copy2[j] + copy2[j*i]) % MOD } pf[i] = 0 } } res := make([]int, n+1) for i := 0; i < n+1; i++ { res[i] = copy1[i] * copy2[i] % MOD } for i := 2; i < n+1; i++ { if pf[i] == 0 { for j := 1; j < n/i+1; j++ { res[j] = (res[j] - res[j*i] + MOD) % MOD } } } return res[1:] }