【LittleXi】蚂蚁9.1笔试题解

20分钟AK速通了

第一题签到略

第二题

题意

给一个长度为n-1的段，q次询问，每次询问两种操作

1、1 x 切割段的x位置

2、2 x 询问最长段是否超过x

题解：

可以考虑开两个有序多重集合，集合sem维护所有的段的长度 ， 集合sep 维护所有切割出来的段的左右端点[l,r]

然后

查询1就是队sep进行lowwer_bound操作一下，找到第一个包含x的位置，然后删除这个段，插入[p.first , x ] 和 [x + 1, p.second]

查询2就是查sem中的最大值是否超过x就行

代码：

import sys
import bisect

def solve():
    input = sys.stdin.read
    data = input().split()
    
    n = int(data[0])
    q = int(data[1])
    
    sem = []
    sep = []
    
    sem.append(n - 1)
    sep.append((1, n))
    
    index = 2
    
    for _ in range(q):
        op = int(data[index])
        x = int(data[index + 1])
        index += 2
        if op == 2:
            mx = sem[-1]
            if mx >= x:
                print("YES")
            else:
                print("NO")
        else:
            idx = bisect.bisect_left(sep, (x, n + 1)) - 1
            p = sep[idx]
            
            if p[0] == x:
                continue
            
            sep.pop(idx)
            sem.pop(idx)
            
            # Insert the two new segments
            sep.insert(idx, (p[0], x))
            sem.insert(idx, x - p[0])
            
            sep.insert(idx + 1, (x, p[1]))
            sem.insert(idx + 1, p[1] - x)

if __name__ == "__main__":
    solve()

第三题

题意

给一个数字n，查找有多少个x，使得gcd(n,x) = x

因为n很大，所以n的给出方式是 $n = b_1 ^ {c _1} * b_2 ^ {c _2} * b_3 ^ {c 3} * ... * b{n-1} ^ {c _{n-1}} * b_n ^ {c _n} $

题解：

可以发现 gcd(n,x) = x <=> n%x == 0 ， 即找n的因子有多少个

那么其实很简单了，假设都是素数，那么答案就是 , 那么如果不是质数呢，我们就手动分解为质数就可以了

代码：

// 第三题
mod = 998244353

def solve():
    m = int(input())
    vp = [tuple(map(int, input().split())) for _ in range(m)]
    mp = {}

    for b, c in vp:
        i = 2
        while i * i <= b:
            if b % i == 0:
                while b % i == 0:
                    if i in mp:
                        mp[i] = (mp[i] + c) % mod
                    else:
                        mp[i] = c % mod
                    b //= i
                i = 1 
            i += 1

        if b >= 2:
            if b in mp:
                mp[b] = (mp[b] + c) % mod
            else:
                mp[b] = c % mod

    ans = 1
    for key in mp:
        ans = (ans * (mp[key] + 1)) % mod

    print(ans)

if __name__ == "__main__":
    solve()

♥关注LittleXi，谢谢喵，ACM金牌选手， 更新更多题解♥

♥算法辅导可以联系我♥