https://www.acwing.com/problem/content/91/
// 乘法快速幂
package main
import (
"fmt"
)
func main() {
var a, b, p int64
fmt.Scanf("%d %d %d", &a, &b, &p)
ans := qpow_for_mod(a, b, p)
fmt.Println(ans)
}
// 循环快速幂 取模
func qpow_for_mod(a, n, mod int64) int64 {
ans := int64(1 % mod)
for n > 0 {
if n&1 == 1 { // n的末位为1,用来判断奇偶性
ans = int64(ans * a % mod)
}
a = int64(a * a % mod)
n >>= 1
}
return ans
}
https://www.acwing.com/problem/content/92/
package main
import (
"fmt"
)
func main() {
var a, b, mod int64
fmt.Scanf("%d\\n%d\\n%d", &a, &b, &mod)
fmt.Println(_64multiply(a, b, mod))
}
// 64位数乘法
func _64multiply(a, b, mod int64) (ans int64) {
for ; b > 0; b >>= 1 {
if b&1 == 1 {
ans = (ans + a) % mod
}
a = a * 2 % mod
}
return
}
https://www.acwing.com/problem/content/93/
package main
import (
"fmt"
)
const N int = 20
const M int = 1 << N
var f [M][N]int
var weight [N][N]int
var n int
// acwing 91
func main() {
fmt.Scan(&n)
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
fmt.Scan(&weight[i][j])
}
}
for i := 0; i < M; i++ {
for j := 0; j < N; j++ {
f[i][j] = 1<<32 - 1
}
}
f[1][0] = 0
for i := 0; i < 1<<n; i++ { // i表示所有的情况
for j := 0; j < n; j++ { // j表示走到哪一个点
if i>>j&1 == 1 {
for k := 0; k < n; k++ { // k表示走到j这个点之前,以k为终点的最短距离
if i>>k&1 == 1 {
f[i][j] = min_i(f[i][j], f[i-(1<<j)][k]+weight[k][j])
}
}
}
}
}
fmt.Println(f[(1<<n)-1][n-1])
}
func min_i(a, b int) int {
if a < b {
return a
}
return b
}
https://www.acwing.com/problem/content/94/
package main
import (
"fmt"
)
var n int
func main() {
fmt.Scan(&n)
back(0, 0)
}
func back(u, state int) {
if u == n {
for i := 0; i < n; i++ {
if state>>i&1 == 1 {
fmt.Print(i+1, " ")
}
}
fmt.Println()
return
}
back(u+1, state)
back(u+1, state|1<<u)
}