CDEF题解

爱音开灯 
class PrimeTable:
    def __init__(self, n=int((10**9)**0.5)+3) -> None:
        self.n = n
        self.primes = [] 
        self.min_div = [0] * (n+1)
        self.min_div[1] = 1
 
        mu = [0] * (n+1)
        phi = [0] * (n+1)
        mu[1] = 1
        phi[1] = 1
 
        for i in range(2, n+1):
            if not self.min_div[i]:
                self.primes.append(i)
                self.min_div[i] = i
                mu[i] = -1
                phi[i] = i-1
            for p in self.primes:
                if i * p > n: break
                self.min_div[i*p] = p
                if i % p == 0:
                    phi[i*p] = phi[i] * p
                    break
                else:
                    mu[i*p] = -mu[i]
                    phi[i*p] = phi[i] * (p - 1)

    def is_prime(self, x:int):
        if x < 2: return False
        if x <= self.n: return self.min_div[x] == x
        for p in self.primes:
            if p * p > x: break
            if x % p == 0: return False
        return True

    def prime_factorization(self, x:int):
        for p in self.primes:
            if p * p > x: break
            if x <= self.n: break
            if x % p == 0:
                cnt = 0
                while x % p == 0: cnt += 1; x //= p
                yield p, cnt
        while (1 < x and x <= self.n):
            p, cnt = self.min_div[x], 0
            while x % p == 0: cnt += 1; x //= p
            yield p, cnt
        if x >= self.n and x > 1:
            yield x, 1

    def get_factors(self, x:int):
        factors = [1]
        for p, b in self.prime_factorization(x):
            n = len(factors)
            for j in range(1, b+1):
                for d in factors[:n]:
                    factors.append(d * (p ** j))
        return factors

pt=PrimeTable(10**6+5)
n,x=map(int,input().split())
tot=0
for p in pt.get_factors(x):
    if p<=n:
        tot+=1
if tot%2==0:
    print("OFF")
else:
    print("ON")
一个数会翻转所有倍数的状态
则一个数会翻转自己因子个数次
统计x没超过n的因子个数
偶数关闭，奇数开启


小灯做题 
t=int(input())
for _ in range(t):
    a,b,c,k=map(int,input().split())
    if k in [a,b,c]:
        print(0)
    elif k==0:
        print(1)
    elif k==1:
        if 0 in [a,b,c]:
            print(1)
        else:
            print(2)
    elif k==2:
        if (0 in [a,b,c]) and (1 in [a,b,c]):
            print(1)
        elif (0 in [a,b,c])&nbs***bsp;(1 in [a,b,c]):
            print(2)
        else:
            print(3)
    else:
        print(-1)
考虑mex的特性
要么k就在[a,b,c]中，要么k只能是0,1,2
没0造0，没1造1，没2造2


立希喂猫
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
q=int(input())
tmp=list(range(n))
su=sum(a)
tmp.sort(key=lambda x:-b[x])
query=[]
for i in range(q):
    k=int(input())
    query.append([i,k])
res=[0]*q
query.sort(key=lambda x:x[1])
pre=0
for i,k in query:
    while tmp and b[tmp[-1]]<k:
        x=tmp.pop()
        pre+=a[x]*b[x]
        su-=a[x]
    res[i]=su*k+pre
for i in res:
    print(i)
最贪的吃法，每天把所有种类的猫粮都吃一次
吃k天的话，数量小于k的猫粮就不够吃了，所以要全吃
数量大于等于k的猫粮够吃，所以是每天都吃一次
前缀和+二分就可以了，当然我这里离线回答了一下复杂度是一样的


祥子拆团 
from math import comb
class PrimeTable:
    def __init__(self, n=int((10**9)**0.5)+3) -> None:
        self.n = n
        self.primes = []
        self.min_div = [0] * (n+1)
        self.min_div[1] = 1
 
        mu = [0] * (n+1)
        phi = [0] * (n+1)
        mu[1] = 1
        phi[1] = 1
 
        for i in range(2, n+1):
            if not self.min_div[i]:
                self.primes.append(i)
                self.min_div[i] = i
                mu[i] = -1
                phi[i] = i-1
            for p in self.primes:
                if i * p > n: break
                self.min_div[i*p] = p
                if i % p == 0:
                    phi[i*p] = phi[i] * p
                    break
                else:
                    mu[i*p] = -mu[i]
                    phi[i*p] = phi[i] * (p - 1)

    def is_prime(self, x:int):
        if x < 2: return False
        if x <= self.n: return self.min_div[x] == x
        for p in self.primes:
            if p * p > x: break
            if x % p == 0: return False
        return True

    def prime_factorization(self, x:int):
        for p in self.primes:
            if p * p > x: break
            if x <= self.n: break
            if x % p == 0:
                cnt = 0
                while x % p == 0: cnt += 1; x //= p
                yield p, cnt
        while (1 < x and x <= self.n):
            p, cnt = self.min_div[x], 0
            while x % p == 0: cnt += 1; x //= p
            yield p, cnt
        if x >= self.n and x > 1:
            yield x, 1
            
    def get_factors(self, x:int):
        factors = [1]
        for p, b in self.prime_factorization(x):
            n = len(factors)
            for j in range(1, b+1):
                for d in factors[:n]:
                    factors.append(d * (p ** j))
        return factors

pt=PrimeTable(10**6+1)
mod=10**9+7
t=int(input())
for _ in range(t):
    x,k=map(int,input().split())
    ans=1
    for p,n in pt.prime_factorization(x):
        ans*=comb(n+k-1,n)
        ans%=mod
    print(ans)
要把x分解成k个正整数相乘，先放k个1，看作是k个不同的盒子
然后质因数分解，对于每一种质因子分别计算答案，再乘法原理乘起来
对于一种质数因子，如果有n个，那么问题相当于是把n个完全相同的小球，放入k个不同的盒子中，盒子可空的方案数
这是一个经典的组合数学问题，网上一搜一堆，我就直接略过给出答案了 comb(n+k-1,n)

这个问题太过经典，有很多变式，可以练习一下
lc 2338. 统计理想数组的数目
https://atcoder.jp/contests/arc004/tasks/arc004_4