CF 数论做题笔记

CF1114C Trailing Loves

首先从 $10$ 进制开始分析。求 $p$ 末尾 $0$ 的数量即为求 $p$ 的因数中含有 $2$ 和 $5$ 的数量的最小值。

例如设 $x_1=2^3\times 5^2$，则 $x_1$ 的末尾 $0$ 的数量即为 $\min(3,2)=2$。

接下来考虑 $(n!)_b$ 的末尾 $0$ 的数量。我们先枚举 $b$ 的因数 $b=p_1^{a_1}\times p_2^{a_2}\times \ldots \times p_k^{a_k}$，若 $p_i^{m}$ 是 $n!$ 的一个因数，则其对答案的贡献为 $\lfloor \dfrac{m}{a_i}\rfloor$。

const int N=2e6+10;
int n,b;
int pri[N],cnt=0;
int t[N];
int ans=INF;
signed main()
{
    n=read();b=read();
    for(int i=2;i*i<=b;i++)
    {
        if(b%i==0)
        {
            pri[++cnt]=i;
            while(b%i==0) b/=i,t[cnt]++;
        }
    }
    if(b>1) pri[++cnt]=b,t[cnt]++;
    for(int i=1;i<=cnt;i++)
    {
        int nt=n;
        int sum=0;
        while(nt)
        {
            sum+=nt/pri[i];
            nt/=pri[i];
        }
        ans=min(sum/t[i],ans);
    }
    printf("%lld\n",ans);
    return 0;
}

CF1493D GCD of an Array

由于一个集合的最大公因数的一个质因数的指数是这个集合中该质数指数的最小值，可以想到每次动态维护集合 gcd 时，考虑将 $y$ 分解质因数 $y=p_1^{e_1}\times p_2^{e_2}\times \ldots \times p_k^{e_k}$，如果集合中除 $a_x$ 以外的其他元素均有可以对答案产生贡献的因数 $p_i$，那么答案就可以加入 $p_i$ 产生的贡献。

形式化的，如果我们定义 $v_p(a_i)$ 为 $a_i$ 中质因数 $p$ 的指数，那么若满足

$$\min(v_p(a_1), \ldots, v_p(a_{x-1}), v_p(y), v_p(a_{x+1}), \ldots, v_p(a_n)) > \min(v_p(a_1), v_p(a_2), \ldots, v_p(a_n))$$

设 $A$ 为上述两式的差值，则对答案的贡献为 $p^A$。

接下来考虑如何求。可以用线性筛预处理质数，每次操作用预处理的最小质因子分解。

我们用 multiset 记录质数 $p$ 出现在的元素下标，$t$ 数组记录 $p$ 在多少个不同的元素中出现。当执行一次操作时，判断是否能够给答案产生贡献。如果能，那么插入当前的下标，随后暴力将 multiset 中的 $1\sim n$ 下标删除一次。

const int N=2e5+10;
int n,m;
int a[N];
multiset<int> st[N];
int b[N];
int prime[N];
int cnt=0;
int t[N];
int ans=1;
void pri(int n)
{
    for(int i=2;i<=n;i++)
    {   
        if(!b[i]) b[i]=i,prime[++cnt]=i;
        for(int j=1;j<=cnt;j++)
        {
            if(prime[j]>b[i] || prime[j]>n/i) break;
            b[i*prime[j]]=prime[j];
        }
    }
}
void modify(int p,int x)
{
    while(x!=1)
    {
        int minn=b[x];
        if(st[minn].find(p)==st[minn].end()) t[minn]++;
        st[minn].insert(p);
        if(t[minn]==n)
        {
            for(int i=1;i<=n;i++)
            {
                st[minn].erase(st[minn].find(i));
                if(st[minn].find(i)==st[minn].end()) t[minn]--;
            }
            ans=(ans*minn)%mod;
        }
        x/=minn;
    }
}
signed main()
{
    pri(N-1);
    n=read();m=read();
    for(int i=1;i<=n;i++)
    {
        a[i]=read();
    }
    for(int i=1;i<=n;i++)
    {
        modify(i,a[i]);
    }
    while(m--)
    {
        int p=read(),x=read();
        modify(p,x);
        printf("%lld\n",ans);
    }
    return 0;
}