当前位置： 首页 > news >正文

商丘建网站爱站查询工具

news 2025/8/11 22:42:46
商丘建网站,爱站查询工具,找题做的网站,电商店铺整除分块十分naive&#xff0c;但是卡常之后就不清真了。 常数优化也是一门技术啊&#xff01; 如果需要计算\[\sum_{i1}^n\lfloor \frac{n}{i} \rfloor\] 有一个naive的做法就是 for (long long i1,la; i<n; ila1){lan/(n/i);ans(n/i)*(la-i1); } 但是&#xff0c;这样不仅…

整除分块十分naive，但是卡常之后就不清真了。

常数优化也是一门技术啊！

如果需要计算\[\sum_{i=1}^n\lfloor \frac{n}{i} \rfloor\]
有一个naive的做法就是

for (long long i=1,la; i<=n; i=la+1){la=n/(n/i);ans+=(n/i)*(la-i+1);
}

但是，这样不仅根号有2的常数，瓶颈上还有3次除法（可优化至2次），如果n是一个较大的数，跑起来很man。
今天突然看到了松1自己的提交，于是兴冲冲地又复习了一下优越的算法。
首先推式子
要求\[\sum_{i=1}^n \sum_{j=1}^n [i*j \leq n] \]
可拆为\[ \sum_{i=1}^{ \lfloor \sqrt {n} \rfloor} \sum_{j=1}^n [i*j \leq n] +\sum_{i= \lfloor \sqrt{n} \rfloor +1}^n \sum_{j=1}^n [i*j \leq n] \]
变换边界条件\[ \sum_{i=1}^{ \lfloor \sqrt {n} \rfloor} \sum_{j=1}^n [i*j \leq n] +\sum_{i= \lfloor \sqrt{n} \rfloor +1}^n \sum_{j=1}^{\lfloor \sqrt{n} \rfloor} [i*j \leq n] \]
在把前后两项变得一样
\[ \sum_{i=1}^{ \lfloor \sqrt {n} \rfloor} \sum_{j=1}^n [i*j \leq n] +\sum_{i=1}^n \sum_{j=1}^{\lfloor \sqrt{n} \rfloor} [i*j \leq n]-\sum_{i=1}^{ \lfloor \sqrt {n} \rfloor} \sum_{j=1}^{\lfloor \sqrt {n} \rfloor}[i*j \leq n]\]
合并一下
\[2* \sum_{i=1}^{\lfloor \sqrt {n} \rfloor} \sum_{j=1}^n [i*j \leq n] - ( \lfloor \sqrt{n} \rfloor)^2 \]
换一种表示
\[2* \sum_{i=1}^{\lfloor \sqrt{n} \rfloor} \lfloor \frac{n}{i} \rfloor -(\lfloor \sqrt{n} \rfloor) ^2 \]
就可以快速计算啦！

%:pragma GCC target("avx")
%:pragma GCC optimize(3)
%:pragma GCC optimize("Ofast")
%:pragma GCC optimize("inline")
%:pragma GCC optimize("-fgcse")
%:pragma GCC optimize("-fgcse-lm")
%:pragma GCC optimize("-fipa-sra")
%:pragma GCC optimize("-ftree-pre")
%:pragma GCC optimize("-ftree-vrp")
%:pragma GCC optimize("-fpeephole2")
%:pragma GCC optimize("-ffast-math")
%:pragma GCC optimize("-fsched-spec")
%:pragma GCC optimize("unroll-loops")
%:pragma GCC optimize("-falign-jumps")
%:pragma GCC optimize("-falign-loops")
%:pragma GCC optimize("-falign-labels")
%:pragma GCC optimize("-fdevirtualize")
%:pragma GCC optimize("-fcaller-saves")
%:pragma GCC optimize("-fcrossjumping")
%:pragma GCC optimize("-fthread-jumps")
%:pragma GCC optimize("-funroll-loops")
%:pragma GCC optimize("-fwhole-program")
%:pragma GCC optimize("-freorder-blocks")
%:pragma GCC optimize("-fschedule-insns")
%:pragma GCC optimize("inline-functions")
%:pragma GCC optimize("-ftree-tail-merge")
%:pragma GCC optimize("-fschedule-insns2")
%:pragma GCC optimize("-fstrict-aliasing")
%:pragma GCC optimize("-fstrict-overflow")
%:pragma GCC optimize("-falign-functions")
%:pragma GCC optimize("-fcse-skip-blocks")
%:pragma GCC optimize("-fcse-follow-jumps")
%:pragma GCC optimize("-fsched-interblock")
%:pragma GCC optimize("-fpartial-inlining")
%:pragma GCC optimize("no-stack-protector")
%:pragma GCC optimize("-freorder-functions")
%:pragma GCC optimize("-findirect-inlining")
%:pragma GCC optimize("-frerun-cse-after-loop")
%:pragma GCC optimize("inline-small-functions")
%:pragma GCC optimize("-finline-small-functions")
%:pragma GCC optimize("-ftree-switch-conversion")
%:pragma GCC optimize("-foptimize-sibling-calls")
%:pragma GCC optimize("-fexpensive-optimizations")
%:pragma GCC optimize("-funsafe-loop-optimizations")
%:pragma GCC optimize("inline-functions-called-once")
%:pragma GCC optimize("-fdelete-null-pointer-checks")
#include <iostream>
#include <cmath>
using namespace std;
typedef unsigned long long ll;
int main(){ll n; cin>>n;ll ans=0;ll p=sqrt(n);for (ll i=p; i; --i) ans+=n/i;ans=ans*2-p*p;cout<<ans<<endl;
}

还不够快？
利用\[ \lfloor \frac{n}{2i} \rfloor =\lfloor \frac{\lfloor \frac{n}{i} \rfloor}{2} \rfloor \]
可以优化

%:pragma GCC target("avx")
%:pragma GCC optimize(3)
%:pragma GCC optimize("Ofast")
%:pragma GCC optimize("inline")
%:pragma GCC optimize("-fgcse")
%:pragma GCC optimize("-fgcse-lm")
%:pragma GCC optimize("-fipa-sra")
%:pragma GCC optimize("-ftree-pre")
%:pragma GCC optimize("-ftree-vrp")
%:pragma GCC optimize("-fpeephole2")
%:pragma GCC optimize("-ffast-math")
%:pragma GCC optimize("-fsched-spec")
%:pragma GCC optimize("unroll-loops")
%:pragma GCC optimize("-falign-jumps")
%:pragma GCC optimize("-falign-loops")
%:pragma GCC optimize("-falign-labels")
%:pragma GCC optimize("-fdevirtualize")
%:pragma GCC optimize("-fcaller-saves")
%:pragma GCC optimize("-fcrossjumping")
%:pragma GCC optimize("-fthread-jumps")
%:pragma GCC optimize("-funroll-loops")
%:pragma GCC optimize("-fwhole-program")
%:pragma GCC optimize("-freorder-blocks")
%:pragma GCC optimize("-fschedule-insns")
%:pragma GCC optimize("inline-functions")
%:pragma GCC optimize("-ftree-tail-merge")
%:pragma GCC optimize("-fschedule-insns2")
%:pragma GCC optimize("-fstrict-aliasing")
%:pragma GCC optimize("-fstrict-overflow")
%:pragma GCC optimize("-falign-functions")
%:pragma GCC optimize("-fcse-skip-blocks")
%:pragma GCC optimize("-fcse-follow-jumps")
%:pragma GCC optimize("-fsched-interblock")
%:pragma GCC optimize("-fpartial-inlining")
%:pragma GCC optimize("no-stack-protector")
%:pragma GCC optimize("-freorder-functions")
%:pragma GCC optimize("-findirect-inlining")
%:pragma GCC optimize("-frerun-cse-after-loop")
%:pragma GCC optimize("inline-small-functions")
%:pragma GCC optimize("-finline-small-functions")
%:pragma GCC optimize("-ftree-switch-conversion")
%:pragma GCC optimize("-foptimize-sibling-calls")
%:pragma GCC optimize("-fexpensive-optimizations")
%:pragma GCC optimize("-funsafe-loop-optimizations")
%:pragma GCC optimize("inline-functions-called-once")
%:pragma GCC optimize("-fdelete-null-pointer-checks")
%:pragma GCC target("sse2,sse3,ssse3,sse4")
#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;
int main(){ll n; cin>>n;ll ans=0;ll p=sqrt(n),z=n/p;for (ll i=1; i<=p; i+=2){ll t=n/i;while (t>=z){ans+=t;t>>=1;}}ans=ans*2-p*p;cout<<ans;
}

还不够快，减少一次判断？

#pragma GCC target("avx")
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC target("sse2,sse3,ssse3,sse4")
#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;
int main(){ll n; cin>>n;ll ans=0;ll p=sqrt(n),z=n/p;for (ll i=1,t=n; i<=p; t=n/(i+=2))do{ans+=t;}while ((t>>=1)>=z);ans=ans*2-p*p;cout<<ans;
}

显然这还是没有到极致，不过我觉得已经挺快了。
1e16在机房的普通台式机上只需0.5s
还不够快？优化除法次数吧！

#pragma GCC target("avx")
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC target("sse2,sse3,ssse3,sse4")
#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;
#define C 13
int main(){ll n; cin>>n;ll ans=0;ll p=sqrt(n),z=n/p;for (ll i=1,t=n,la=n+C; i<=p;){ll tmp=t;do{ans+=tmp;}while ((tmp>>=1)>=z);if (la-t<C){la=t;i+=2;ll g=i*(--t);while (g>n){--t;g-=i;}}else{la=t;t=n/(i+=2);}}ans=ans*2-p*p;cout<<ans;
}

现在1e16只需0.38s左右

这东西貌似有一个\(log\)做法，先咕着。

转载于:https://www.cnblogs.com/Yuhuger/p/9940189.html

http://www.lbrq.cn/news/2665549.html

相关文章：

  • 做外贸怎么登陆国外网站如何自己做网络推广
  • php做不了大型网站关键词的选取原则
  • 合肥做网站价格太原seo关键词优化
  • 短网站生成万网商标查询
  • wordpress 名片插件河南seo网站多少钱
  • 高端网站建设专业营销团队什么软件可以优化关键词
  • 手机音乐网站源码网络营销软件代理
  • 沃尔玛网上超市seo工作内容和薪资
  • 专业做化妆品的网站2345浏览器下载安装
  • 网站建设交流qq电商软文范例100字
  • 网址大全介绍福州排名seo公司
  • 百度商桥怎么接网站合肥网站优化搜索
  • 招工网站服务百度网页推广怎么做
  • 钟祥网页设计哪家公司做推广优化好
  • 郑州市科协网站百度seo关键词优化推荐
  • 做网站要不要用jsp南京企业网站排名优化
  • 域名备案网站备案兰州压热搜
  • 校园网站方案和生活app下载安装最新版
  • 怎样设计网站百度站长平台网页版
  • wordpress用了cdn和缓存插件网站编辑seo
  • 鞍山网站建设为什么seo工资不高
  • 用asp做网站的可行性分析上海推广外包
  • 编程工具西安seo顾问公司
  • 做水电到哪个网站找信息百度商城app
  • 苏州做网站外包的公司app地推接单平台有哪些
  • 网站图一般做多少分辨率宁波seo博客
  • asp.net做的网站多合一seo插件破解版
  • 一个网站上线需要什么sem培训班培训多少钱
  • 幼儿园网站模板 asphao123网址大全浏览器设为主页
  • 墨刀网页设计详细教程天津优化公司哪家好
  • 【模板】拓扑排序
  • 人工智能-python-机器学习-决策树与集成学习：决策树分类与随机森林
  • Python与MySQL数据库交互实践：自动化数据插入系统
  • vue如何监听localstorage
  • C语言指针完全指南：从入门到精通
  • MCU-基于TC397的启动流程