BZOJ 3944 Sum

时间:2022-08-13 22:36:32

题目链接:Sum

  嗯……不要在意……我发这篇博客只是为了保存一下杜教筛的板子的……

  你说你不会杜教筛?唐老师(其实我不认识)写了一篇讲的非常好的博客,看完应该就会了……

  这道题就是杜教筛板子题,也没什么好讲的……

  下面贴代码(不知道为什么我的常数就是大):

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
#define maxn 5664511 using namespace std;
typedef long long llg; int pr[maxn],T,n,lp;
bool vis[maxn],vu[1300],vp[1300];
llg mu[maxn],phi[maxn],su[1300],sp[1300]; void pre(){
mu[1]=phi[1]=1;
for(int i=2;i<maxn;i++){
if(!vis[i]) pr[++lp]=i,mu[i]=-1,phi[i]=i-1;
for(int j=1;j<=lp && pr[j]*i<maxn;j++){
vis[i*pr[j]]=1;
if(i%pr[j]!=0) mu[i*pr[j]]=-mu[i],phi[i*pr[j]]=phi[i]*phi[pr[j]];
else{phi[i*pr[j]]=phi[i]*pr[j];break;}
}
}
for(int i=2;i<maxn;i++) mu[i]+=mu[i-1],phi[i]+=phi[i-1];
} llg solveu(int x){
if(x<maxn) return mu[x];
if(vu[n/x]) return su[n/x];
llg now=1; vu[n/x]=1;
for(int i=2,nt=0;nt<x;i=nt+1) nt=x/(x/i),now-=(nt-i+1)*solveu(x/i);
return su[n/x]=now;
} llg solvep(llg x){
if(x<maxn) return phi[x];
if(vp[n/x]) return sp[n/x];
llg now=x*(llg)(x+1); now>>=1;
for(int i=2,nt=0;nt<x;i=nt+1) nt=x/(x/i),now-=(nt-i+1)*solvep(x/i);
vp[n/x]=1; return sp[n/x]=now;
} int main(){
File("a");
scanf("%d",&T); pre();
while(T--){
scanf("%d",&n);
memset(vu,0,sizeof(vu));
memset(vp,0,sizeof(vp));
printf("%lld %lld\n",solvep(n),solveu(n));
}
return 0;
}

BZOJ 3944 Sum的更多相关文章

  1. ●杜教筛入门&lpar;BZOJ 3944 Sum&rpar;

    入门杜教筛啦. http://blog.csdn.net/skywalkert/article/details/50500009(好文!) 可以在$O(N^{\frac{2}{3}})或O(N^{\f ...

  2. BZOJ 3944&colon; Sum &lbrack;杜教筛&rsqb;

    3944: Sum 贴模板 总结见学习笔记(现在还没写23333) #include <iostream> #include <cstdio> #include <cst ...

  3. bzoj 3944&colon; Sum(杜教筛)

    3944: Sum Time Limit: 10 Sec  Memory Limit: 128 MBSubmit: 4930  Solved: 1313[Submit][Status][Discuss ...

  4. BZOJ&period;3944&period;Sum&lpar;Min&lowbar;25筛&rpar;

    BZOJ 洛谷 不得不再次吐槽洛谷数据好水(连\(n=0,2^{31}-1\)都没有). \(Description\) 给定\(n\),分别求\[\sum_{i=1}^n\varphi(i),\qu ...

  5. bzoj 3944 Sum —— 杜教筛

    题目:https://www.lydsy.com/JudgeOnline/problem.php?id=3944 杜教筛入门题! 看博客:https://www.cnblogs.com/zjp-sha ...

  6. BZOJ 3944 Sum 解题报告

    我们考虑令: \[F_n = \sum_{d|n}\varphi(d)\] 那么,有: \[\sum_{i=1}^{n}F_i = \sum_{i=1}^{n}\sum_{d|i}\varphi(d) ...

  7. 【刷题】BZOJ 3944 Sum

    Description Input 一共T+1行 第1行为数据组数T(T<=10) 第2~T+1行每行一个非负整数N,代表一组询问 Output 一共T行,每行两个用空格分隔的数ans1,ans ...

  8. 「bzoj 3944&colon; Sum」

    题目 杜教筛板子了 #include<iostream> #include<cstring> #include<cstdio> #include<cmath& ...

  9. bzoj 3944&colon; Sum【莫比乌斯函数&plus;欧拉函数&plus;杜教筛】

    一道杜教筛的板子题. 两个都是积性函数,所以做法是一样的.以mu为例,设\( f(n)=\sum_{d|n}\mu(d) g(n)=\sum_{i=1}^{n}f(i) s(n)=\sum_{i=1} ...

随机推荐

  1. node中的cmd规范

    你应该熟悉nodejs模块中的exports对象,你可以用它创建你的模块.例如:(假设这是rocker.js文件) exports.name = function() { console.log('M ...

  2. Map&period;Entry用法示例

    一般在HashMap中可以通过key值得到value值,以key作为检索项.Map.Entry<K,V>可以作为条目的检索项.HashMap中有entrySet()方法,返回值是Set&l ...

  3. unity3D对象的显示和隐藏

    SetActive/active/SetActiveRecursively 后两者比较旧,现在通常用第一个SetActive 必须先new一个gameobject对象用于实例化,然后再设置其activ ...

  4. python 笔记2--函数

    函数变量 >>> a = abs # 变量a指向abs函数 >>> a(-1) # 所以也可以通过a调用abs函数 1 定义函数 def my_abs(x): if ...

  5. Linux常用操作命令(二)

    ab命令压测: ab -n 1 -c 1 -p post.txt -T 'application/x-www-form-urlencoded' -H 'User-U:2Lh72GM2UumEAnZzM ...

  6. JAVA 用数组实现 ArrayList

    我们知道 ArrayList 是一个集合,它能存放各种不同类型的数据,而且其容量是自动增长的.那么它是怎么实现的呢? 其实 ArrayList 的底层是用 数组实现的.我们查看 JDK 源码也可以发现 ...

  7. 【Alpha】Scrum Meeting 4

    目录 前言 任务分配 燃尽图 会议照片 签入记录 困难 前言 第4次会议在4月8日由PM在教一317召开. 对项目完成情况进行了确认,分配下一阶段任务.时长60min. 任务分配 姓名 当前阶段任务 ...

  8. 非抢占式RCU中的一些概念

    该记录着重介绍下:2.6.34版本中非抢占式RCU的基本概念. RCU保护的是指针,因为指针的赋值可以使用原子操作完成: 在非抢占式RCU中: 对于读者,RCU仅需要抢占失效,因此获得读锁和释放读锁分 ...

  9. 2017-2018-2 20179207 《网络攻防技术》第十三周作业 python3实现SM234算法

    国密算法SM234 的python3实现 国家标准 GM/T 0002-2012 <SM4分组密码算法> GM/T 0003.1-2012 <SM2椭圆曲线公钥密码算法 第1部分:总 ...

  10. 20145329 《Java程序设计》实验一总结

    实验指导教师:娄嘉鹏老师 实验日期:2016.4.8 实验时间:16:30~18:30 实验序号:实验一 实验名称:Java开发环境的熟悉 实验目的与要求: 使用JDK编译.运行简单的Java程序. ...