BZOJ 2005 [Noi2010]能量采集 ——Dirichlet积
2024-09-04 10:34:41
【题目分析】
卷积一卷。
然后分块去一段一段的求。
O(n)即可。
【代码】
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define maxn 100005
#define ll long long
#define F(i,j,k) for (ll i=j;i<=k;++i)
ll n,m,pr[maxn],top,d;
ll phi[maxn]; void init()
{
F(i,2,maxn-1)
{
if (!phi[i]) pr[++top]=i,phi[i]=i-1;
for (ll j=1;j<=top&&(ll)pr[j]*i<(ll)maxn;++j)
{
if (i%pr[j]==0) {phi[i*pr[j]]=phi[i]*pr[j];break;}
else phi[i*pr[j]]=phi[i]*phi[pr[j]];
}
}
} int main()
{
init();
scanf("%d%d",&n,&m);
F(i,1,maxn-1) phi[i]+=phi[i-1];
ll ans=0;
ll la,lb,nowa,nowb,l,r=n;
while (r)
{
nowa=n/r; nowb=m/r;
la=n/(nowa+1)+1;lb=m/(nowb+1)+1;
l=max(la,lb);
ans+=(ll)nowa*nowb*(phi[r]-phi[l-1]);
r=l-1;
}
printf("%lld\n",n*m+2*ans);
}
最新文章
- 安装sitecore数据库和客户端到本机
- Ionic学习笔记三 Gulp在ionic中的使用
- 转:Caused by: java.lang.NoSuchMethodError: org.apache.log4j.Category.log
- React快速入门
- MVP+RXJAVA+RecyclerView实现sd卡根目录下的所有文件中的照片加载并显示
- 新建一个DataTable(只针对一列)
- 【CF】283D Tennis Game
- Maven配置 settings.xml 转
- 远程连接MySQL 不允许
- 【设计模式】单例模式 Singleton Pattern
- deque源码4(deque元素操作:pop_back、pop_front、clear、erase、insert)
- 大杀器:VS2017 查看或调试liunx代码(转载)
- solr安装配置(一)
- hadoop实现倒排索引
- python入门 -- 学习笔记2
- Lucene创建索引流程
- 在linux环境下,php语法出错,怎样让php编译后提示编译错误,错误在哪?
- [UE4]需要保存的数据
- Linux定时任务 结合PHP实现实时监控
- 关于ie7下display:inline-block;不支持的解决方案