题目链接: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的更多相关文章
-
●杜教筛入门(BZOJ 3944 Sum)
入门杜教筛啦. http://blog.csdn.net/skywalkert/article/details/50500009(好文!) 可以在$O(N^{\frac{2}{3}})或O(N^{\f ...
-
BZOJ 3944: Sum [杜教筛]
3944: Sum 贴模板 总结见学习笔记(现在还没写23333) #include <iostream> #include <cstdio> #include <cst ...
-
bzoj 3944: Sum(杜教筛)
3944: Sum Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 4930 Solved: 1313[Submit][Status][Discuss ...
-
BZOJ.3944.Sum(Min_25筛)
BZOJ 洛谷 不得不再次吐槽洛谷数据好水(连\(n=0,2^{31}-1\)都没有). \(Description\) 给定\(n\),分别求\[\sum_{i=1}^n\varphi(i),\qu ...
-
bzoj 3944 Sum —— 杜教筛
题目:https://www.lydsy.com/JudgeOnline/problem.php?id=3944 杜教筛入门题! 看博客:https://www.cnblogs.com/zjp-sha ...
-
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) ...
-
【刷题】BZOJ 3944 Sum
Description Input 一共T+1行 第1行为数据组数T(T<=10) 第2~T+1行每行一个非负整数N,代表一组询问 Output 一共T行,每行两个用空格分隔的数ans1,ans ...
-
「bzoj 3944: Sum」
题目 杜教筛板子了 #include<iostream> #include<cstring> #include<cstdio> #include<cmath& ...
-
bzoj 3944: Sum【莫比乌斯函数+欧拉函数+杜教筛】
一道杜教筛的板子题. 两个都是积性函数,所以做法是一样的.以mu为例,设\( f(n)=\sum_{d|n}\mu(d) g(n)=\sum_{i=1}^{n}f(i) s(n)=\sum_{i=1} ...
随机推荐
-
node中的cmd规范
你应该熟悉nodejs模块中的exports对象,你可以用它创建你的模块.例如:(假设这是rocker.js文件) exports.name = function() { console.log('M ...
-
Map.Entry用法示例
一般在HashMap中可以通过key值得到value值,以key作为检索项.Map.Entry<K,V>可以作为条目的检索项.HashMap中有entrySet()方法,返回值是Set&l ...
-
unity3D对象的显示和隐藏
SetActive/active/SetActiveRecursively 后两者比较旧,现在通常用第一个SetActive 必须先new一个gameobject对象用于实例化,然后再设置其activ ...
-
python 笔记2--函数
函数变量 >>> a = abs # 变量a指向abs函数 >>> a(-1) # 所以也可以通过a调用abs函数 1 定义函数 def my_abs(x): if ...
-
Linux常用操作命令(二)
ab命令压测: ab -n 1 -c 1 -p post.txt -T 'application/x-www-form-urlencoded' -H 'User-U:2Lh72GM2UumEAnZzM ...
-
JAVA 用数组实现 ArrayList
我们知道 ArrayList 是一个集合,它能存放各种不同类型的数据,而且其容量是自动增长的.那么它是怎么实现的呢? 其实 ArrayList 的底层是用 数组实现的.我们查看 JDK 源码也可以发现 ...
-
【Alpha】Scrum Meeting 4
目录 前言 任务分配 燃尽图 会议照片 签入记录 困难 前言 第4次会议在4月8日由PM在教一317召开. 对项目完成情况进行了确认,分配下一阶段任务.时长60min. 任务分配 姓名 当前阶段任务 ...
-
非抢占式RCU中的一些概念
该记录着重介绍下:2.6.34版本中非抢占式RCU的基本概念. RCU保护的是指针,因为指针的赋值可以使用原子操作完成: 在非抢占式RCU中: 对于读者,RCU仅需要抢占失效,因此获得读锁和释放读锁分 ...
-
2017-2018-2 20179207 《网络攻防技术》第十三周作业 python3实现SM234算法
国密算法SM234 的python3实现 国家标准 GM/T 0002-2012 <SM4分组密码算法> GM/T 0003.1-2012 <SM2椭圆曲线公钥密码算法 第1部分:总 ...
-
20145329 《Java程序设计》实验一总结
实验指导教师:娄嘉鹏老师 实验日期:2016.4.8 实验时间:16:30~18:30 实验序号:实验一 实验名称:Java开发环境的熟悉 实验目的与要求: 使用JDK编译.运行简单的Java程序. ...