x∈[1,n],y∈[1,m]}中素数的个数.解题思路:
很好想到
设f(d)=∑x=1n∑y=1m[gcd(x,y)=p] (其中P为素数,[] 括号内式子成立为1,否则0)
设F(d)=∑x=1n∑y=1m[d∣gcd(x,y)]同时F(d)=[dn][dm]
显然F(n)=∑d∣nf(d)
两种形式反演后得到
$f(d) = \sum _{d|n}\mu(\frac{n}{d})F(d) $ (1)
$f(n) = \sum _{d|n}\mu(d)F(\frac{n}{d}) $ (2)
我们取(1)式
f(d)=∑d∣nμ(dn)[dn][dm] (1)
最终结果就是
ans=∑pmin(n,m)f(p)=∑pmin(n,m)∑d=1min(n,m)/pμ(d)[dn/p][dm/p]
直接计算复杂度太高 显然不可取。
令t = pk;
∑pmin(n,m)∑d=1min(n,m)/pμ(d)[tn][tm]=∑t=1min(n,m)∑pp<=n,p∣t,p为素数μ(pt)[tn][tm]
其中对于∑pp<=n,p∣t,p为素数μ(pt)我们可以在线性筛中预处理出来,然后求其前缀和
最后通过分段优化一下即可,
参考
难死了,看了好久都不是很懂、,(Ps:线性筛真TM强大)
附本题代码
--------------------------------------------------------------------------------------------.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57
| int const MAX = 1e7 + 5; int mob[MAX], p[MAX], g[MAX], sum[MAX]; bool noprime[MAX];
int Mobius() { mob[1] = 1; int pnum = 0; for(int i = 2; i < MAX; i++) { if(!noprime[i]) { p[pnum ++] = i; mob[i] = -1; g[i] = 1; } for(int j = 0; j < pnum && i * p[j] < MAX; j++) { noprime[i * p[j]] = true; if(i % p[j] == 0) { mob[i * p[j]] = 0; g[i * p[j]] = mob[i]; break; } mob[i * p[j]] = -mob[i]; g[i * p[j]] = mob[i] - g[i]; } sum[i] = sum[i - 1] + g[i]; } }
ll cal(int l, int r) { ll ans = 0; if(l > r) swap(l, r); for(int i = 1, last = 0; i <= l; i = last + 1) { last = min(l / (l / i), r / (r / i)); ans += (ll) (l / i) * (r / i) * (sum[last] - sum[i - 1]); } return ans; }
int main() { Mobius(); int T; scanf("%d", &T); while(T--) { int l, r; scanf("%d %d", &l, &r); printf("%lld\n", cal(l, r)); } }
|
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 tabris的博客! 赞助
wechat
alipay