【BZOJ3944】 Sum
2024-09-03 20:31:24
Description
Input
一共T+1行
第1行为数据组数T(T<=10)
第2~T+1行每行一个非负整数N,代表一组询问
Output
一共T行,每行两个用空格分隔的数ans1,ans2
Sample Input
6
1
2
8
13
30
2333
1
2
8
13
30
2333
Sample Output
1 1
2 0
22 -2
58 -3
278 -3
1655470 2
2 0
22 -2
58 -3
278 -3
1655470 2
Solution
裸的杜教筛。具体的内容详见洲阁2015年的集训队论文。这里我就大致口胡一下,求一个积性函数的前缀和可以把它狄利克雷卷积上另一个函数,同时卷上的这个函数和卷完得到的这个函数如果都很好求前缀和的话,那么就可以用杜教筛来求。phi函数大致的推导如下:
Code
#include <cstdio>
#include <map> #define R register
#define maxn 2000010
typedef long long ll;
int phi[maxn], miu[maxn], pr[maxn / ], prcnt;
ll sph[maxn], smi[maxn];
bool vis[maxn];
const int moha = ;
struct Hash {
Hash *next;
int ps; ll ans;
} *last1[moha], *last2[moha], mem[moha], *tot = mem;
inline ll S1(R int n)
{
if (n < maxn) return sph[n];
for (R Hash *iter = last1[n % moha]; iter; iter = iter -> next)
if (iter -> ps == n) return iter -> ans; R ll ret = 1ll * n * (n + 1ll) / ;
for (R ll i = , j; i <= n; i = j + )
{
j = n / (n / i);
ret -= S1(n / i) * (j - i + );
}
*++tot = (Hash) {last1[n % moha], n, ret}; last1[n % moha] = tot;
return ret;
}
inline ll S2(R int n)
{
if (n < maxn) return smi[n];
for (R Hash *iter = last2[n % moha]; iter; iter = iter -> next)
if (iter -> ps == n) return iter -> ans; R ll ret = ;
for (R ll i = , j; i <= n; i = j + )
{
j = n / (n / i);
ret -= (j - i + ) * S2(n / i);
}
*++tot = (Hash) {last2[n % moha], n, ret}; last2[n % moha] = tot;
return ret;
}
int main()
{
R int T; scanf("%d", &T);
phi[] = sph[] = ;
miu[] = smi[] = ;
for (R int i = ; i < maxn; ++i)
{
if (!vis[i]) pr[++prcnt] = i, phi[i] = i - , miu[i] = -;
sph[i] = sph[i - ] + phi[i];
smi[i] = smi[i - ] + miu[i];
for (R int j = ; j <= prcnt && 1ll * i * pr[j] < maxn; ++j)
{
vis[i * pr[j]] = ;
if (i % pr[j])
{
phi[i * pr[j]] = phi[i] * (pr[j] - );
miu[i * pr[j]] = -miu[i];
}
else
{
phi[i * pr[j]] = phi[i] * pr[j];
miu[i * pr[j]] = ;
break;
}
}
}
for (; T; --T)
{
R int N; scanf("%d", &N);
// printf("%d\n", N);
printf("%lld %lld\n", S1(N), S2(N));
}
return ;
}
/*
6
1
2
8
13
30
2333
*/
最新文章
- bzoj 1061 志愿者招募 有上下界费用流做法
- 搭建 Windows Server 2003 + IIS6.0 + FastCGI + PHP5.3.29 + MySQL5.5.38 + Memcached1.2.6
- flash与js交互
- Unity加载模块深度解析(Shader)
- Windows文件系统漏洞
- Database Primary key and Foreign key [From Internet]
- 用一个简单的例子来理解python高阶函数
- php中的引用类型和值类型
- java程序员从笨鸟到菜鸟之(七)一—java数据库操作
- c# webBrowser控件与js的交互
- C#和C++中的float类型
- EF+jQueryUI前后端分离设计
- thrift概述
- Android自定义控件(状态提示图表) (转)
- STM32的IAP实现
- 【转】HTTP
- Linux运维之如何查看目录被哪些进程所占用,lsof命令、fuser命令
- Android的Button按钮,ACTION_UP事件不触发解决方案
- ubuntu17.10安装LAMP并测试部署php探针系统
- webpack 入门总结和实践(按需异步加载,css单独打包,生成多个入口文件)