【min_25筛】筛欧拉函数、莫比乌斯函数、积性函数

传送门:欧拉函数、莫比乌斯函数

花了一下午学了一下min25筛。

一知半解。不过还是学会了套板子。

mu函数要看成质数个数取反,在预处理g的时候不能带负数(我也不知道为什么)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 233;
ll primes[maxn], cnt;
bool st[maxn];
ll sp1[maxn], sp2[maxn], g1[maxn], g2[maxn], sm[maxn], g[maxn], w[maxn], wcnt;
ll id1[maxn], id2[maxn];
ll inv2, inv6, qn;
ll ksm(ll n, ll k)
{
    ll res = 1;
    while(k)
    {
        if(k & 1) res = res * n;
        n = n * n ;
        k >>= 1;
    }
    return res;
}
void get_primes(int n)
{
    for(int i = 
Read the rest

【杜教筛】HUD-6706 huntian oy

传送门

题意:f(n,a,b)=\sum_{i=1}^n \sum_{j=1}^i gcd(i^a-j^a,i^b-j^b)[gcd(i,j)=1]\%(10^9+7)
给定n,a,b求f

打表可知f(n,a,b)=\sum_{i=1}^n \sum_{j=1}^i (i-j)[gcd(i,j)=1]\%(10^9+7)

即:\sum\limits_{i=1}^n\sum\limits_{j=1}^i\ i\ [gcd(i,j)=1]-\sum\limits_{i=1}^n\sum\limits_{j=1}^i\ j\ [gcd(i,j)=1]

在i j互质的时候才有值。前面一部分就是每个数与其互质的个数的和,\sum\limits_{i=1}^{n}i\varphi(i)

后面一部分是每个数,与其互质的数值的和。\sum\limits_{i=1}^{n}\frac{i\varphi(i)}{2}(n1)

原因是gcd(n,x)=gcd(n,n-x),当出现一个与n互质的数x的时候必然有一个n-x成对出现与其互质。他们的和为\frac{n}{2},但这只是在n1的时候成立。

由于n==1的时候只有一个数字1,所以式子完整来写应该是\sum\limits_{i=1}^{n}\frac{i\varphi(i)+1}{2}因为在i=1的时候答案是1,如果除2就成了1/2,所以在分子上加个1使其成立

完整式子是\sum\limits_{i=1}^{n}\frac{i\varphi(i)-1}{2}

由于n有1e9,线筛是存不下的。
考虑
f=i\varphi(i)=id\varphi(i)
g=id
f*g(n)=\sum\limits_{i|n}\varphi(i)i\frac{n}{i}=n\sum\limits_{i|n}\varphi(i)

然后套杜教筛的板子。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e6 + 233;
typedef long long ll;
const ll mod = 1e9 + 7;
ll inv2, inv6;
bool st[maxn];
int primes[maxn], cnt;
ll phi[maxn];
unordered_map<int, ll> up;
ll ksm(ll n, ll k)
{
    
Read the rest

【数论】线筛积性函数/莫比乌斯反演

传送门

题意:
f(n) = \sum\limits_i^n\sum\limits_j^n\phi(gcd(i,j)),给定T<=5000组询问,每次n<=1e9

将公式化简可以得到(省略反演步骤)

ans = \sum\limits_p\sum\limits_{p|d}\mu(\frac{d}{p})\lfloor\frac{n}{d}\rfloor\lfloor\frac{n}{d}\rfloor\phi(p)
ans = \sum\limits_p\sum\limits_{d=1}\mu(d)\lfloor\frac{n}{dp}\rfloor\lfloor\frac{n}{dp}\rfloor\phi(p)

此时将内层整除移动到外层,设dp = T

ans = \sum\limits_T\lfloor\frac{n}{T}\rfloor\lfloor\frac{n}{T}\rfloor\sum\limits_{p|T}\mu(\frac{T}{p})\phi(p)

h(T) = \sum\limits_{p|T}\mu(\frac{T}{p})\phi(p),想办法处理这个函数的前缀和,与前面整除分块一起计算

观察到这是莫比乌斯函数和欧拉函数的迪利克雷卷积,所以h也是一个积性函数。既然是积性函数,那么可由若互质的因子的函数值相乘得到。

考虑h(pri^x)其中pri为T的一个质因子,x为质因子的个数。由于莫比乌斯函数的自变量只要有两个以上的相同质因子,函数值就为零。观察上面的卷积式子。那么只有当p = pri^xp = pri^{x-1}的时候,\mu分别为1和-1。即此时\frac{T}{p}=1,\frac{T}{p}=p。所以
h(pri^x) = \phi(pri^x) – \phi(pri^{x-1})

此时就可以线筛了。

线筛的方法如下:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e7 + 233;
int st[maxn];
ll primes[maxn], f[maxn], h[maxn], phi[maxn], low[maxn], cnt;
void get_primes(ll n)
{
    f[1] 
Read the rest

【欧拉函数】acwing221

传送门

解法:欧拉函数

俗话说数论上来先打表,打完表智力就正常了

我先打了一张n为50的表
//1 2 1 2 5 2 1 2 1 10 1 2 1 2 5 2 1 2 1 10 1 2 1 2 25 2 1 2 1 10 1 2 1 2 5 2 1 2 1 10 1 2 1 2 5 2 1 2 1 50
发现gcd好像有很多重复的数字

gcd为1的就是与50互质的数,个数为\phi{(N)}

gcd为2的个数怎么算?仔细想想,对于每一个gcd(i,N) = d的数对,都存在gcd(i/d , N/d) = 1
也就是说,对于每个数对,各自除以gcd和N都是互质的,那么很明显数对的个数为\phi{(N/d)}

有了以上结论,可以想到,N的所有gcd的可能性就是N的所有约数,对于每个约数,数对的个数为\phi{(N/d)}个,它们的和就是d\phi{(N/d)}

进一步总结,答案就是\sum_{d|N}d\phi{(N/d)}

这个函数是两个积性函数的迪利克雷卷积,所以是个积性函数,有xxxx的性质,可以线筛等等

然而我一看数据范围2^31那比不可能线筛,只能暴力算了。… Read the rest