ICPC2018 沈阳网络赛 C.Convex Hull
题目链接
https://nanti.jisuanke.com/t/A1991
题目大意
定义 $gay(i)$ 函数在 $i$ 含有平方因子时为 $0$ ，否则为 $i ^ 2$
你需要计算：
$$\sum\limits_{num=1}^n (\sum\limits_{i=1}^{num} gay(i)) \mod p $$
题目分析
首先可以将这个函数进行化简，化简为
$$\sum\limits_{i=1}^n\sum\limits_{j=1}^i\mu^2(j)j ^ 2$$
换为考虑统计每个数出现的次数，那么可以化为
$$\sum\limits_{i=1}^n\mu^2(i)i ^ 2(n – i + 1)$$
展开可以得到
$$\sum\limits_{i=1}^n((n + 1)\mu^2(i)i ^ 2 – \mu^2(i)i ^ 3)$$
再考虑求$\sum\limits_{i=1}^n\mu^2(i)i ^ 2$
使用容斥将所有的平方因子都去掉即可，容斥因子显然为 $\mu(i)$
因此可化为
$$\sum\limits_{i=1}^{\sqrt{n}}\mu(i)\sum\limits_{j=1}^{\lfloor\frac{n}{i ^ 2}\rfloor}(ji^2)^2$$
即
$$\sum\limits_{i=1}^{\sqrt{n}}\mu(i)i^4\sum\limits_{j=1}^{\lfloor\frac{n}{i ^ 2}\rfloor}j^2$$
同理 $i^3$ 的式子也可以这样处理，得到
$$\sum\limits_{i=1}^{\sqrt{n}}\mu(i)i^6\sum\limits_{j=1}^{\lfloor\frac{n}{i ^ 2}\rfloor}j^3$$
用平方和及立方和公式求和即可。
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <map>
#include <unordered_map>
using namespace std;
const int maxn = 1e5 + 5;
const int m = 1e5;
long long n, k, p;
int prime[maxn];
bool isnp[maxn];
long long u[maxn];
long long f[maxn];
long long g[maxn];
int pc = 0;
long long mul(__int128 x, __int128 y){
return x * y % p;
//如果用下面注释里面的会 TLE……
/*long long ret = 0;
long long k = x / 10000000ll;
ret = (ret + 10000000ll * y % p * k) % p;
x %= 10000000ll;
ret = (ret + x * y) % p;
return ret;*/
}
int init(){
int i, j;
u[1] = 1;
for(i=2;i<=m;i++){
if(!isnp[i]){
pc++;
prime[pc] = i;
u[i] = -1;
}
for(j=1;j<=pc and i * prime[j]<=m;j++){
isnp[i * prime[j]] = true;
if(i % prime[j] == 0){
u[i * prime[j]] = 0;
break;
}else{
u[i * prime[j]] = -u[i];
}
}
}
return 0;
}
long long suma(long long x){
long long ret = f[x];
x = n / x / x;
long long a = x, b = x + 1, c = 2 * x + 1;
if(a % 2 == 0){
a /= 2;
}else if(b % 2 == 0){
b /= 2;
}else{
c /= 2;
}
if(a % 3 == 0){
a /= 3;
}else if(b % 3 == 0){
b /= 3;
}else{
c /= 3;
}
ret = mul(mul(ret, a), mul(b, c));
return ret;
}
long long sumb(long long x){
long long ret = g[x];
x = n / x / x;
long long a = x, b = x + 1;
if(a % 2 == 0){
a /= 2;
}else{
b /= 2;
}
ret = mul(ret, mul(mul(a, a), mul(b, b)));
return ret;
}
int main(){
long long i, j;
long long ans = 0;
init();
while(~scanf("%lld%lld", &n, &p)){
ans = 0;
for(i=1;i*i<=n;i++){
f[i] = u[i] * mul(mul(i, i), mul(i, i));
g[i] = u[i] * mul(mul(mul(i, i), mul(i, i)), mul(i, i));
}
for(i=1;i*i<=n;i++){
ans = (ans + (mul(n + 1, suma(i)) - sumb(i)) % p + p) % p;
}
printf("%lld\n", ans);
}
return 0;
}