acm竞赛中国赛区参赛队名单（acm竞赛中国赛区赛程）

首先，对于某个质数 pp ，如果 p|np|n 且 p2|np^2|n ,那么答案一定为0。

接下来我们考虑如何解决 nn 不存在平方质因子的情况。

我们尝试对Min_25筛的第二部分做一些改动：

设 P_{j}, gcd(i,n)=1,i不存在平方质因子 \right]}">的最小质因子不存在平方质因子S(m,j)=∑i=1mμ(i)[i的最小质因子>Pj,gcd(i,n)=1,i不存在平方质因子]S(m,j)=\sum_{i=1}^{m}{\mu(i)\left[ i的最小质因子>P_{j}, gcd(i,n)=1,i不存在平方质因子 \right]} ,

那么最终的答案就是 (S(m,0)+1)∗μ(n)(S(m,0)+1)*\mu(n) 。

根据上面对 S(m,j)S(m,j) 的定义，我们可以得到如下转移方程：

S(m,j)=−∑Pj<p≤m[gcd(n,p)=1]+∑k>j,Pk≤m,gcd(Pk,n)=1μ(Pk)∗S(m/Pk,k)S(m,j)=-\sum_{P_{j}<p\leq m}^{}{\left[ gcd(n,p)=1 \right]}+\sum_{k>j,P_{k}\leq m,gcd(P_{k},n)=1}^{}{\mu(P_{k})*S(m/P_{k},k)} 。

对于质数贡献，我们可以使用Min_25筛的第一部分预处理出前缀质数个数，由于 nn 的质数不会超过20个，我们可以直接遍历 nn 的每个质数来求出区间 [Pj+1,m]\left[ P_{j}+1 , m\right] 内不合法的 pp 的数量。

至于合数贡献，直接根据公式递归计算即可。

代码如下：

#include<bits/stdc++.h>using namespace std; #define IOS ios::sync_with_stdio(0),cin.tie(0) #define endl \n typedef long long ll; const int N = 2e6 + 10; ll m, n; bool v[N]; int prime[N], tot; void sieve(int n){ v[1] = 1; for (int i = 2;i <= n;++i){ if (!v[i])prime[++tot] = i; for (int j = 1;j <= tot && prime[j] <= n / i;++j){ v[i * prime[j]] = 1; if (i % prime[j] == 0)break; } } } ll w[N], cnt; ll g[N]; int sq; int id1[N], id2[N]; vector<ll>np; // n的质因子 void calc_g(){ // 求区间[2,m]中质数个数 for (ll l = 1, r;l <= m;l = r + 1){ r = m / (m / l); w[++cnt] = m / l; g[cnt] = w[cnt] - 1; m / r <= sq ? id1[m / r] = cnt : id2[r] = cnt; } for (int i = 1;i <= tot;++i) for (int j = 1;j <= cnt && prime[i] <= w[j] / prime[i];++j){ int p = w[j] / prime[i]; p = p <= sq ? id1[p] : id2[m / p]; g[j] = g[j] - (g[p] - (i - 1)); } } ll calc_s(ll x, ll y){ if (prime[y] >= x)return 0; int p = x <= sq ? id1[x] : id2[m / x]; // 计算质数贡献 ll ans = y - g[p]; // ans += upper_bound(np.begin(), np.end(), x) - upper_bound(np.begin(), np.end(), prime[y]); for (auto now : np) ans += (prime[y] < now && now <= w[p]); // 计算合数贡献 for (int i = y + 1;i <= tot && prime[i] < x / prime[i];++i) if (!v[prime[i]]) ans += -1 * calc_s(x / prime[i], i); return ans; } signed main(){ #ifdef FSLSE freopen("in.in", "r", stdin); freopen("out.out", "w", stdout); #endif IOS; cin >> m >> n; sq = sqrt(m); sieve(sq); ll tmp = n; for (int i = 2;i <= n / i;++i) if (tmp % i == 0){ tmp /= i; np.push_back(i); v[i] = 1; if (tmp % i == 0){ cout << 0 << endl; return 0; } } if (tmp != 1){ np.push_back(tmp); if (tmp <= sq)v[tmp] = 1; // 小心数组越界 } calc_g(); ll ans = calc_s(m, 0) + 1; if (np.size() & 1)ans *= -1; cout << ans << endl; return 0; }