Alphaville

158

Apricity_1

ican

geekby

Alphaville
51分钟前
package main

import (
"bufio"
"fmt"
"os"
)

func gcd(a, b int) int {
if b != 0 {
return gcd(b, a%b)
} else {
return a
}
}

func main() {

var n int
fmt.Fscanln(in, &n)

var a, b int
for n > 0 {
n--
fmt.Fscanln(in, &a, &b)
fmt.Println(gcd(a, b))
}
}


Alphaville
2小时前
package main

import (
"bufio"
"fmt"
"os"
)

const mod int = 1e9 + 7

var primes map[int]int

func main() {
primes = make(map[int]int)

var n int
fmt.Fscanln(in, &n)

var a int
for n > 0 {
n--
fmt.Fscanln(in, &a)
for i := 2; i <= a/i; i++ {
for a%i == 0 {
a /= i
primes[i]++
}
}
if a > 1 {
primes[a]++
}
}

res := 1
for p, exp := range primes {
t := 1
for exp > 0 {
exp--
t = (p*t + 1) % mod
}
res = (res * t) % mod
}

fmt.Println(res)
}


Alphaville
5小时前
package main

import (
"bufio"
"fmt"
"os"
)

const mod int = 1e9 + 7

var primes map[int]int

func main() {
primes = make(map[int]int)

var n int
fmt.Fscanln(in, &n)

var a int
for n > 0 {
n--
fmt.Fscanln(in, &a)
for i := 2; i <= a/i; i++ {
for a%i == 0 {
a /= i
primes[i]++
}
}
if a > 1 {
primes[a]++
}
}
res := 1
for _, exp := range primes {
res = res * (exp + 1) % mod
}
fmt.Println(res)
}


Alphaville
18小时前
package main

import (
"bufio"
"fmt"
"os"
"sort"
)

func getDivisors(n int) []int {

var res []int
for i := 1; i <= n/i; i++ {
if n%i == 0 {
res = append(res, i)
if i != n/i {
res = append(res, n/i)
}
}
}
sort.Sort(sort.IntSlice(res))

return res
}

func main() {

var n int
fmt.Fscanln(in, &n)

var x int
for n > 0 {
n--
fmt.Fscanln(in, &x)
t := getDivisors(x)
for _, v := range t {
fmt.Print(v, " ")
}
fmt.Println()
}
}


package main

import (
"bufio"
"fmt"
"os"
)

func divide(n int) {

// 1. 算数基本定理
// 2. n至多有一个大于sqrt(n)的质因子
// 因此i迭代到n/i后，需单独对n进行判断
for i := 2; i <= n/i; i++ {
if n%i == 0 {
cnt := 0
for n%i == 0 {
n /= i
cnt++
}
fmt.Println(i, cnt)
}
}
if n > 1 {
fmt.Println(n, "1")
}
fmt.Println()
}

func main() {

var n int
fmt.Fscanln(in, &n)

var a int
for n > 0 {
n--
fmt.Fscanln(in, &a)
divide(a)
}

}


package main

import (
"bufio"
"fmt"
"os"
)

func isPrime(n int) bool {

if n < 2 {
return false
}
for i := 2; i <= n/i; i++ {
if n%i == 0 {
return false
}
}
return true
}

func main() {
var n int
fmt.Fscanln(in, &n)

var a int
for n > 0 {
n--
fmt.Fscanln(in, &a)
if isPrime(a) {
fmt.Println("Yes")
} else {
fmt.Println("No")
}
}
}



***
st[] 和 match[] 的作用

package main

import (
"bufio"
"fmt"
"os"
)

const (
N int = 510
M int = 100010
)

var (
h         [N]int
e, ne     [M]int
idx       int
match     [N]int
st        [N]bool
n1, n2, m int
)

func memsetRepeat(a []int, v int) {
if len(a) == 0 {
return
}
a[0] = v
for bp := 1; bp < len(a); bp *= 2 {
copy(a[bp:], a[:bp])
}
}

func resetBool(a []bool, v bool) {
if len(a) == 0 {
return
}
a[0] = v
for bp := 1; bp < len(a); bp *= 2 {
copy(a[bp:], a[:bp])
}
}

e[idx] = b
ne[idx] = h[a]
h[a] = idx
idx++
}

func find(x int) bool {

for i := h[x]; i != -1; i = ne[i] {
j := e[i]
if !st[j] {
st[j] = true
if match[j] == 0 || find(match[j]) {
match[j] = x
return true
}
}
}
return false
}

// 时间复杂度 O(n*m)
func main() {
memsetRepeat(h[:], -1)

fmt.Fscanf(in, "%d %d %d\r\n", &n1, &n2, &m)

var x, y int
for m > 0 {
m--
fmt.Fscanf(in, "%d %d\r\n", &x, &y)
}

res := 0
for i := 1; i <= n1; i++ {
resetBool(st[:], false)
if find(i) == true {
res++
}
}

fmt.Println(res)
}


package main

import (
"bufio"
"fmt"
"os"
)

const (
N int = 100010
M int = N * 2
)

var (
h     [N]int
e, ne [M]int
color [N]int
idx   int
n, m  int
)

func memsetRepeat(a []int, v int) {
if len(a) == 0 {
return
}
a[0] = v
for bp := 1; bp < len(a); bp *= 2 {
copy(a[bp:], a[:bp])
}
}

e[idx] = b
ne[idx] = h[a]
h[a] = idx
idx++
}

func dfs(u, c int) bool {

color[u] = c
// 对每个邻接点进行染色
for i := h[u]; i != -1; i = ne[i] {
j := e[i]
if color[j] == 0 {
if dfs(j, 3-c) == false {
return false
}
// 如果一条边两端的点颜色相同，则染色异常
} else if color[j] == c {
return false
}
}
return true
}

func main() {
memsetRepeat(h[:], -1)

fmt.Fscanf(in, "%d %d\r\n", &n, &m)

var x, y int
for m > 0 {
m--
fmt.Fscanf(in, "%d %d\r\n", &x, &y)
}

var flag bool = true
// 对每个点（其实就是对该点所在的连通图）进行染色
// 每个点都正常染色时，保持flag==true成立
for i := 1; i <= n; i++ {
if color[i] == 0 {
if dfs(i, 1) == false {
flag = false
break
}
}
}
if flag == false {
fmt.Println("No")
} else {
fmt.Println("Yes")
}
}


package main

import (
"bufio"
"fmt"
"os"
"sort"
)

const (
N int = 200010
)

type Edge struct {
a, b, w int
}

type edges []Edge

var (
// 并查集：某个点的祖先结点
p    [N]int
es   edges
n, m int
)

func (es edges) Len() int {
return len(es)
}

func (es edges) Less(i, j int) bool {
return es[i].w < es[j].w
}

func (es edges) Swap(i, j int) {
es[i], es[j] = es[j], es[i]
}

func find(x int) int {
if p[x] != x {
p[x] = find(p[x])
}
return p[x]
}

func kruskal() int {
res, cnt := 0, 0

for i := 1; i <= n; i++ {
p[i] = i
}

sort.Sort(es)
// 0...m-1表示按边由小到大排序后的结果
for i := 0; i < m; i++ {
a, b, w := es[i].a, es[i].b, es[i].w
pa, pb := find(a), find(b)
// 当a,b属于不同连通块的时候，且为当前最短边长
// 将a->b加入生成树，cnt边数++
// 自动排除了自环情况
if pa != pb {
res += w
p[pa] = pb
cnt++
}
}

// n个点的无向连通图，生成树应有n-1条边
// 小于n-1，表示原图不是无向连通图，也就不存在最小生成树
if cnt < n-1 {
return -1
} else {
return res
}
}

func main() {

fmt.Fscanf(in, "%d %d\r\n", &n, &m)
es = make(edges, m)

var a, b, w int
for i := 0; i < m; i++ {
fmt.Fscanf(in, "%d %d %d\r\n", &a, &b, &w)
es[i] = Edge{a, b, w}
}

if res := kruskal(); res == -1 {
fmt.Println("impossible")
} else {
fmt.Println(res)
}
}


package main

import (
"bufio"
"fmt"
"os"
)

const (
N   int = 510
INF int = 0x3f3f3f3f
)

var (
g    [N][N]int
dist [N]int
// 是否属于连通图
st   [N]bool
n, m int
)

func memsetRepeat(a []int, v int) {
if len(a) == 0 {
return
}
a[0] = v
for bp := 1; bp < len(a); bp *= 2 {
copy(a[bp:], a[:bp])
}
}

func min(a, b int) int {
if a < b {
return a
} else {
return b
}
}

func prim() int {

res := 0
for i := 0; i < n; i++ {
t := -1
for j := 1; j <= n; j++ {
if st[j] == false && (t == -1 || dist[t] > dist[j]) {
t = j
}
}
// 判断除初始结点外，是否有不连通的点，即是否为连通图
if i != 0 && dist[t] == INF {
return INF
}
// 先将 t 到集合的边加入集合，然后用其更新临边（更新的过程也比较了g[t][j]与之前其他点到集合的距离）
// 防止当 j=t 时，也即防止出现边为负值的自环情况，导致dist[t]变小（相当于将自环加入了最小生成树）
// 所以顺序不能颠倒
if i != 0 {
res += dist[t]
}
for j := 1; j <= n; j++ {
dist[j] = min(dist[j], g[t][j])
}
st[t] = true
}
return res
}

func main() {
memsetRepeat(dist[:], INF)

fmt.Fscanf(in, "%d %d\r\n", &n, &m)

for i := 1; i <= n; i++ {
for j := 1; j <= n; j++ {
g[i][j] = INF
}
}

var a, b, w int
for m > 0 {
m--
fmt.Fscanf(in, "%d %d %d\r\n", &a, &b, &w)
// 去重边，只保留边权最小的边
// 但会引入负边权的自环(是否与题干的不含负环相矛盾，因为属于特殊的负环)
minValue := min(g[a][b], w)
g[a][b], g[b][a] = minValue, minValue
}

if t := prim(); t == INF {
fmt.Println("impossible")
} else {
fmt.Println(t)
}
}