ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 正文

[牛客竞赛数学专题班积性函数]C.序列(莫比乌斯反演 + 线性筛)

2022年11月24日 162点热度 0人点赞 0条评论

题目链接:C-序列_牛客竞赛数学专题班积性函数(积性函数概念、欧拉筛求积性函数、莫比乌斯反演) (nowcoder.com)

Pre-Knowledge

前置知识:《莫比乌斯反演入门以及简单例题讲解》

Problem

给定两个长度为\(n\)的数组\(a\)和\(b\),求下面这个和式的值:

$$\sum\limits_{x=1}^n\sum\limits_{y=1}^n[gcd(x,y)=1][a_{b_x} = b_{a_y}]$$

根据莫反套路,设两个函数:

$$F(n):当gcd(x, y)为n的倍数时[a_{b_x} = b_{a_y}]的对数$$

$$f(n):当gcd(x,y)=n时[a_{b_x} = b_{a_y}]的对数$$

定义完之后就可以得到两个函数的关系了:

$$F(n) = \sum\limits_{n|d}f(d)$$

开始莫反!

$$f(n) = \sum\limits_{n|d}\mu( \frac{d}{n})F(d)$$

我们要求的\(ans = f(1)\),所以:

$$ans = f(1) = \sum\limits_{d=1}^n \mu(d) F(d)$$

将\(d\)用\(i\)换掉:

$$ans = \sum\limits_{i=1}^n \mu(i) F(i)$$

现在只需要处理出\(\mu\)和\(F\)两个函数即可。

\(\mu\)可以通过线性筛直接筛出来,\(F\)函数可以通过一个\(O(nlogn)\)的算法算出来。

枚举\(i\)和\(i的倍数j\),此时一定满足条件\(gcd(i, j) = k * i\),接下来记录\(a_{b_j}\)的出现次数,再将\(b_{a_j}\)出现的次数加入到\(F(i)\)中。

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5 + 9;
//杜教筛+线性筛优化,复杂度O(N^(2/3))
int mu[maxn], a[maxn], b[maxn], F[maxn], cnt[maxn];

void init(int N = maxn - 1)//N = maxn - 1
{
    bitset<maxn> vis;
    vector<int> prim;
    vis[0] = vis[1] = true;
    mu[1] = 1;
    for(int i = 2;i <= N; ++ i)
    {
        if(!vis[i])prim.push_back(i), mu[i] = -1;
        
        for(auto &j : prim)
        {
            if(i * j > N)break;
            vis[i * j] = true;
            if(i % j == 0)break;
            mu[i * j] = mu[i] * mu[j];
        }
    }
}

signed main()
{
	int n;scanf("%lld", &n);
	init(n);
	for(int i = 1;i <= n; ++ i)scanf("%lld", a + i);
	for(int i = 1;i <= n; ++ i)scanf("%lld", b + i);
	
    for(int i = 1;i <= n; ++ i)
    {
        for(int j = i;j <= n;j += i)cnt[a[b[j]]] ++;
        for(int j = i;j <= n;j += i)F[i] += cnt[b[a[j]]];
        for(int j = i;j <= n;j += i)cnt[a[b[j]]] = 0;
    }
    
	int ans = 0;
	for(int i = 1;i <= n; ++ i)ans += mu[i] * F[i];
	printf("%lld\n", ans);
	return 0;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: C++ 数论 牛客网 积性函数 算法竞赛 莫比乌斯反演
最后更新:2022年11月27日

Eriktse

19岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌选手,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

订阅本站
Loading
文章目录
  • Pre-Knowledge
  • Problem
  • Code

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

赣ICP备2022001555号-1

赣公网安备 36092402000057号