【LittleXi】蚂蚁9.1笔试题解

【LittleXi】蚂蚁9.1笔试题解

20分钟AK速通了

第一题签到略

第二题

题意

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

1、1 x 切割段的x位置

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

n < 1e9 , q < 1e5

题解:

可以考虑开两个有序多重集合,集合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的因子有多少个

那么其实很简单了,假设b_i都是素数,那么答案就是(1+c_1) * (1+c_2) * ... * (1+c_n) , 那么如果b_i不是质数呢,我们就手动分解为质数就可以了

代码:

// 第三题
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金牌选手, 更新更多题解♥

♥算法辅导可以联系我♥

全部评论
膜大佬,第二题就写了半天😭
1 回复 分享
发布于 09-01 20:31 四川
吐了 第三题没有对分解做mod 卡10%
1 回复 分享
发布于 09-01 20:48 北京
膜拜大佬
点赞 回复 分享
发布于 09-01 20:40 广东
二十分钟。。。金牌✌🏻就是金牌✌🏻
点赞 回复 分享
发布于 09-01 20:48 安徽
不愧是金牌🥇,瓦达西~杂鱼喵
点赞 回复 分享
发布于 09-01 20:53 山东
20分钟我都抄不完这个代码😭
点赞 回复 分享
发布于 09-01 20:54 北京
佬太强了
点赞 回复 分享
发布于 09-01 21:07 浙江
第三题思路一样但是只过了50,不知道为啥,没时间debug了
点赞 回复 分享
发布于 09-01 23:45 重庆
你们发的笔试有时间点吗,我的为啥是没有时间点要求,这几天天天给我发,好像打开就能做
点赞 回复 分享
发布于 09-02 10:36 北京

相关推荐

12 12 评论
分享
牛客网
牛客企业服务