Description：

求 $1\sim n$ 中有多少数字满足以下三个条件之一：是 $b$ 的倍数，是 $m$ 个质数中任意一个的倍数， $f(x)=1$

$f(x)$ 的定义如下： $f$ 是积性函数，且 $f(1)=1$ ， $f(p^k)=r_k$ 。

$1\leqslant n\leqslant 10^{10}$

## Solution：

首先是比较显然的 $\min\_25$ 筛，考虑递归处理的那部分，我们实际上是枚举了所有数的最小质因子以及它的出现次数，然后统计已经被消成质数的数的贡献，那么整体来看实际上是枚举了一个数除了大于 $\sqrt n$ 的质因子之外的其他质因子计算他们的贡献，然后对大于 $\sqrt n$ 的质因子预处理 $g(n,j)$ 计算，这个过程可以看作是从小的质因子向大的质因子进行数位 $DP$ 的过程，那么我们也可以用类似数位 $DP$ 的方法做。设 $S(n,j,nr,v,rem)$ 表示在 $[1,n]$ 中， $minp\geqslant p_j$ ，前面所有质因子的贡献的 $r$ 的乘积为 $nr$ ，前面的质因子是否出现过 $a$ 中的数 $v$ ，还要再乘 $rem$ 才能是 $b$ 的倍数，然后转移的时候和 $\min\_25$ 筛一样，先是计算质数的贡献，这个需要预处理一个质数个数以及质数的和，然后再枚举最小质因子以及它的指数，考虑质数的贡献，如果 $f\ne 0||v||rem==1$ ，那么说明已经满足条件了，所有的大于等于 $p_j$ 的质数都合法，贡献就是 $g(n,|p|)-(j-1)$ ，否则的话贡献就是所有大于等于 $p_j$ 的给出来的质数的个数，如果 $rem$ 是质数（合数肯定不行），并且满足 $rem$ 在合法范围 $[prime[j],n]$ 之间，那么也就是说可以选这个质数作为最后一个质数，那么还要加上 $1$ ，注意如果 $rem$ 也是 $m$ 个数之一就不加一。这道题也压根就没有什么积性函数，但是他巧妙地运用了 $\min\_25$ 筛法对素因子进行统计。

对 $rem$ 可以暴力判断是不是质数，反正 $rem$ 只有 $\sigma_0(b)$ 个。

Code：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

ll n,m,b;

#define MAXN 1000010

int r[65];

ll a[MAXN];

ll N;

int id1[MAXN],id2[MAXN];

int& id(ll k){return (k <= N ? id1[k] : id2[n / k]);}

ll w[MAXN];

ll g[MAXN];

bool isprime[MAXN];

int prime[MAXN],tot = 0;

void sieve(int n)

{

	for(int i = 2;i <= n;++i)isprime[i] = true;

	for(int i = 2;i <= n;++i)

	{

		if(isprime[i])prime[++tot] = i;

		for(int j = 1;j <= tot && i * prime[j] <= n;++j)

		{

			isprime[i * prime[j]] = false;

			if(i % prime[j] == 0)break;

		}

	}

	return;

}

bool mark[MAXN];

ll sg[MAXN];

int pos[MAXN];

ll gcd(ll a,ll b){return (b == 0 ? a : gcd(b,a % b));}

map<int,bool> pr;

bool check(ll v)

{

	if(pr.find(v) != pr.end())return pr[v];

	if(v == 1)return false;

	for(int i = 1;1ll * prime[i] * prime[i] <= v;++i)

	{

		if(v % prime[i] == 0)return (pr[v] = false);

	}

	return (pr[v] = true);

}

ll S(ll n,int j,int nr,int v,ll rem)

{

	ll res = 0;

	if(v || rem == 1 || nr * r[1] != 0)res = g[id(n)] - (j - 1);

	else

	{

		res = pos[id(n)] - sg[j - 1];

		if(check(rem) && rem <= n && rem >= prime[j] && !(rem <= N && mark[rem]))++res;

	}

	if(j > tot)return res;

	for(int k = j;k <= tot && 1ll * prime[k] * prime[k] <= n;++k)

	{

		ll p1 = prime[k],p2 = 1ll * prime[k] * prime[k];

		for(int e = 1;p2 <= n;++e,p1 = p2,p2 *= prime[k])

		{

			res += S(n / p1,k + 1,nr * r[e],v | mark[prime[k]],rem / gcd(rem,p1));

			res += ((nr * r[e + 1] != 0) || (v || mark[prime[k]]) || (p2 % rem == 0));

		}

	}

	return res;

} 

int main()

{

	scanf("%lld%lld%lld",&n,&m,&b);

	for(int i = 1;i <= m;++i)scanf("%lld",&a[i]);

	for(int i = 1;i <= 60;++i)scanf("%d",&r[i]);

	N = sqrt(n);

	for(int i = 1;i <= m;++i)if(a[i] <= N)mark[a[i]] = true;

	sieve(N);

	for(ll l = 1,r;l <= n;l = r + 1)

	{

		r = n / (n / l);

		w[++w[0]] = n / l;

		id(n / l) = w[0];

		g[w[0]] = w[w[0]] - 1;

	}

	for(int j = 1;j <= tot;++j)

	{

		for(int i = 1;i <= w[0] && 1ll * prime[j] * prime[j] <= w[i];++i)

		{

			g[i] = g[i] - g[id(w[i] / prime[j])] + j - 1;

		}

	}

	for(int i = 1;i <= tot;++i)sg[i] = sg[i - 1] + mark[prime[i]];

	for(int i = 1;i <= w[0];++i)pos[i] = upper_bound(a + 1,a + 1 + m,w[i]) - a - 1;

	cout << n - S(n,1,1,0,b) - 1 << endl;

	return 0;

}