【题解】牛客挑战赛37F

首先根据裴蜀定理，我们可以得出的实际的步长就是。我们使得，那么所有的都为的因子。
单独考虑个，同时被这个经过的点为，为正整数，令,那么这样的点的个数为，可以计算。
可以发现也为的因子，在的范围内的因子个数大概在级别左右。（可以通过构造再求X的因子个数大致证明一下）。
我们可以通过进行大数分解，求出其所有的质因子，然后一遍得出所有的因子。
计算每个因子被经过的次数，如果这个因子恰好被经过了次，说明其倍数可能也恰好被经过次。
把分解成质因子形式，我们可以通过高维前缀和求出每个因子被经过的次数（高维前缀和就是把每个因子看做一个维度，分开枚举因子避免重复计算的小技巧）。
然后，恰好被经过次的因子系数为，否则系数为。
但是还有考虑重复计数，现假设的一个因子,的一个因子，那么在计算的时候，得到的是所有倍数的点，多计算了倍数为的点，我们需要将的系数减去的系数避免重复计数，这里，我们可以再通过一次高维前缀和得出每个因子应该的系数。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
typedef long long ll;
ll ans;
ll mul(ll a,ll b,ll mod)
{
    return (a*b-(ll)((long double)a/mod*b)*mod+mod)%mod;
}
ll qpow(ll a,ll n,ll mod)
{
    ll ans=1;
    while(n)
    {
        if(n&1) ans=mul(ans,a,mod);
        a=mul(a,a,mod);
        n>>=1;
    }
    return ans;
}
bool mr(ll x,ll b)
{
    ll k=x-1;
    while(k)
    {
        ll cur=qpow(b,k,x);
        if(cur!=1&&cur!=x-1) return false;
        if((k&1)==1||cur==x-1) return true;
        k>>=1;
    }
    return true;
}
bool prim(ll x)//素数测试，如果数据范围大于1e16可以多随机几个素数a进行mr(x,a)测试
{
    if(x==46856248255981ll||x<2) return false;
    if(x==2||x==3||x==7||x==61||x==24251) return true;
    return mr(x,2)&&mr(x,61);
}
ll pr(ll x)
{
    ll s=0,t=0,c=rand()%(x-1)+1;
    int st=0,go=1;
    ll val=1;
    for(go=1;;go<<=1,s=t,val=1)
    {
        for(st=1;st<=go;st++)
        {
            t=(mul(t,t,x)+c)%x;
            val=mul(val,abs(t-s),x);
            if((st%127)==0)
            {
                ll d=__gcd(val,x);
                if(d>1) return d;
            }
        }
        ll d=__gcd(val,x);
        if(d>1) return d;
    }
}
void fac(ll x)
{
    if(x<=ans||x<2) return;
    if(prim(x)) {ans=max(ans,x);return;}
    ll p=x;
    while(p>=x)
        p=pr(x);
    while(x%p==0) x/=p;
    fac(x);fac(p);
}
int n,s;
ll m,k,a[N];
unordered_map<ll,int>vis,id;
vector<pair<ll,int> >p;
vector<ll>fc,f;
void getfac(ll x)
{
    while(x!=1)
    {
        ans=0;fac(x);
        int tot=0;
        while(x%ans==0) x/=ans,tot++;
        p.push_back({ans,tot});
    }
}
void dfs(int up,ll res)
{
    if(up==-1)
    {
        fc.push_back(res);
        return;
    }
    dfs(up-1,res);
    for(int i=1;i<=p[up].second;i++)
    {
        res*=p[up].first;
        dfs(up-1,res);
    }
}
int main()
{
    scanf("%d%lld%lld%d",&n,&m,&k,&s);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]),a[i]=__gcd(a[i],m),vis[a[i]]++;
    getfac(m);
    dfs(p.size()-1,1);
    sort(fc.begin(),fc.end());
    for(int i=0;i<fc.size();i++) id[fc[i]]=i,f.push_back(vis[fc[i]]);
    for(int i=p.size()-1;i>=0;i--)
        for(int j=0;j<fc.size();j++)
        if(fc[j]%p[i].first==0)
        f[j]+=f[id[fc[j]/p[i].first]];//通过高维前缀和计算出每个因子会被经过的次数
    for(int i=0;i<fc.size();i++) f[i]=f[i]==s;//恰好被经过s次的因子，说明这个因子的倍数也会被恰好经过s次
    for(int i=p.size()-1;i>=0;i--)
        for(int j=fc.size()-1;j>=0;j--)
        if(fc[j]%p[i].first==0)
        f[j]-=f[id[fc[j]/p[i].first]];//对于j的一个因子，如果j的一次因子经过了s次，那么计算j的因子的时候会重复计算j的，因子这里要减去重复的，同样通过高维前缀和处理
    ll ans=n==s;
    for(int i=0;i<fc.size();i++) ans+=f[i]*(k/fc[i]);
    printf("%lld\n",ans);
}