【题目分析】

卷积一卷。

然后分块去一段一段的求。

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);
}

  

最新文章

  1. 安装sitecore数据库和客户端到本机
  2. Ionic学习笔记三 Gulp在ionic中的使用
  3. 转:Caused by: java.lang.NoSuchMethodError: org.apache.log4j.Category.log
  4. React快速入门
  5. MVP+RXJAVA+RecyclerView实现sd卡根目录下的所有文件中的照片加载并显示
  6. 新建一个DataTable(只针对一列)
  7. 【CF】283D Tennis Game
  8. Maven配置 settings.xml 转
  9. 远程连接MySQL 不允许
  10. 【设计模式】单例模式 Singleton Pattern
  11. deque源码4(deque元素操作:pop_back、pop_front、clear、erase、insert)
  12. 大杀器:VS2017 查看或调试liunx代码(转载)
  13. solr安装配置(一)
  14. hadoop实现倒排索引
  15. python入门 -- 学习笔记2
  16. Lucene创建索引流程
  17. 在linux环境下,php语法出错,怎样让php编译后提示编译错误,错误在哪?
  18. [UE4]需要保存的数据
  19. Linux定时任务 结合PHP实现实时监控
  20. 关于ie7下display:inline-block;不支持的解决方案

热门文章

  1. jdbc接口的一种类比——打酱油
  2. 卷积网络中的通道(Channel)和特征图
  3. 1653: Champion of the Swordsmanship
  4. 剑指offer44 扑克牌顺序
  5. linux_1
  6. bootstrap下拉菜单(Dropdowns)
  7. viewDidLoad、viewWillAppear、viewWillDisappear
  8. js和JQuery中的获取宽、高、位置等方法整理
  9. perl学习之文件句柄filehandle
  10. 【php】 php 的注释和结束符号之间的关系