数论Tag ArchiveSubscribe

传送门

题意：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^x和p = 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

传送门

解法：欧拉函数

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

我先打了一张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