CF1750D Count GCD

2022-11-09

字数统计: 702 | 阅读时长≈ 3 分钟

题意

有 $T$ 组数据。给出两个整数 $n,m$ 和一个长度为 $n$ 的数组 $a$ ，满足 $1\leq i\leq n,1\leq a_i\leq m$
求出满足 $1\leq i\leq n,1\leq b_i\leq m$ 且 $\gcd(b_1,b_2,\cdots ,b_i)=a_i$ 的 $b$ 数组的数量。答案对 $998244353$ 取模。
数据范围： $1\leq t\leq 100,1\leq n\leq 2\cdot 10^5,1\leq m\leq 10^9$

思路

一道很有意思的简单数学题。

显而易见，如果存在满足条件的 $b$ 数组，那么一定有 $1\leq i<n,a_{i+1}\mid a_i$ 。如何证明呢？我们知道 $\gcd(b_1,b_2,\cdots ,b_{i+1})=\gcd(\gcd(b_1,b_2,\cdots,b_i),b_{i+1})$ ，也就是说 $a_{i+1}=\gcd(a_i,b_{i+1})$ ，便有 $a_{i+1}\mid a_i$ 。

下一步，便是找出每一个 $b_i$ 的可能情况。从刚才的结论来看， $a_{i+1}$ 是 $a_i$ 的因子，那么要让 $a_{i+1}=\gcd(a_i,b_{i+1})$ 需要把 $a_i$ 这个因子挑出去，现在只需要解这个方程：

\gcd(\frac{a_i}{a_{i+1}},\frac{b_{i+1}}{a_{i+1}})=1

现在只要求出 $[1,\lfloor \frac{m}{a_{i+1}} \rfloor]$ 中与 $\frac{a_i}{a_{i+1}}$ 互质的数，只需要找出 $\frac{a_i}{a_{i+1}}$ 的质因数，然后用上容斥原理就好了。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long

const int N=2e5+9,Mod=998244353;
int T,n;
ll m,a[N];

int main(){
    scanf("%d",&T);
    while(T--){
        bool flag=1;
        scanf("%d%lld",&n,&m);
        for(int i=1;i<=n;i++){
            scanf("%lld",&a[i]);
            if(i>1&&a[i-1]%a[i]!=0) flag=0;//判断是否满足条件
        }
        if(!flag){
            printf("0\n");
            continue;
        }
        ll ans=1;
        for(int i=2;i<=n;i++){
            ll d=a[i-1]/a[i],x=m/a[i],y=0;
            vector<ll> num;
            for(int i=2;i*i<=d;i++){//分解质因数
                if(d%i==0){
                    int len=num.size();
                    for(int j=0;j<len;j++) num.push_back(-num[j]*i);//容斥
                    num.push_back(i);
                    while(d%i==0) d/=i;
                }
            }
            if(d>1){//特判
                int len=num.size();
                for(int j=0;j<len;j++) num.push_back(-num[j]*d);
                num.push_back(d);
            }
            for(ll i:num) y+=x/i;
            ans=ans*(x-y)%Mod;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

打赏

版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！