摘要
Title: Acwing 第 95 场周赛
Tag: 约数、线性筛、博弈论

Acwing 第 95 场周赛

A AcWing 4873. 简单计算

题意

给定四个整数 x1,y1,x2,y2，请你计算 max(|x1−x2|,|y1−y2|)
思路

模拟

代码

'''
Author: NEFU AB-IN
Date: 2023-03-31 21:50:42
FilePath: \Acwing\95cp\a\a.py
LastEditTime: 2023-03-31 21:51:38
'''
# import
import sys, math
from collections import Counter, deque
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right

# Final
N = int(1e3 + 10)
INF = int(2e9)

# Define
sys.setrecursionlimit(INF)
read = lambda: map(int, input().split())

# —————————————————————Division line ————————————————————————————————————————

x1, y1 = read()
x2, y2 = read()

print(max(abs(x1 - x2), abs(y1 - y2)))

B AcWing 4874. 约数

题意

如果一个正整数的约数个数恰好为，则称该数为美丽数。
给定 n个正整数 a1,a2,…,an，请你依次判断每个数是否是美丽数。
思路

由算数基本定理就可以退出约数个数的式子
$cnt = (p_1 + 1) * (p_2 + 1) * ...$
如果只有三个约数，除去1和其本身 $n$ ，也就是只有一个质因数因子，也就是 $cnt = p_1 + 1 = 3$ ， $p_1 = 2$ ， $n = p_1 ^ 2$ ，也就是说，n是某个质数的完全平方数
所以，先判断n是不是完全平方数，再判断sqrt(n)是不是质数即可

代码

# import
import sys, math
from collections import Counter, deque
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right

# Final
N = int(1e6 + 10)
INF = int(2e9)

# Define
sys.setrecursionlimit(INF)
read = lambda: map(int, input().split())

# —————————————————————Division line ————————————————————————————————————————
st, prime = [0] * N, []


def init():
    st[0] = st[1] = 1
    for i in range(2, N):
        if st[i] == 0:
            prime.append(i)
        for j in range(len(prime)):
            if i * prime[j] >= N:
                break
            st[i * prime[j]] = 1
            if i % prime[j] == 0:
                break


init()
n, = read()
a = list(read())

for x in a:
    y = int(math.sqrt(x))
    if y * y == x:
        if st[y] == 0:
            print("YES")
        else:
            print("NO")
    else:
        print("NO")

C AcWing 4875. 整数游戏

题意

略
思路

link
直接放网址了，讲的有道理

代码

'''
Author: NEFU AB-IN
Date: 2023-03-31 21:50:42
FilePath: \Acwing\95cp\c\c.py
LastEditTime: 2023-04-01 00:48:47
'''
# import
import sys, math
from collections import Counter, deque
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right

# Final
N = int(1e3 + 10)
INF = int(2e9)

# Define
sys.setrecursionlimit(INF)
read = lambda: map(int, input().split())

# —————————————————————Division line ————————————————————————————————————————


def solve():
    n, = read()
    a = list(read())
    x = min(a)
    print("Alice" if x != a[0] else "Bob")


for _ in range(int(input())):
    solve()

Acwing 第 95 场周赛

A AcWing 4873. 简单计算

题意

思路

代码

B AcWing 4874. 约数

题意

思路

代码

C AcWing 4875. 整数游戏

题意

思路

代码