题目链接:https://loj.ac/problem/528
题目:给定两个正整数N,M,你需要计算ΣΣu(gcd(i,j))^2 mod 998244353 ,其中i属于[1,N],j属于[1,M]
解题思路:
代码:
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
typedef long long ll;
const int maxn=1e7+;
const int mod=;
ll n,m,mu[maxn],sum[maxn],prime[maxn],tot;
void getMobius(int N){
for(int i=;i<=N;i++)prime[i]=;
mu[]=;
for(int i=;i<=N;i++){
if(prime[i]){
prime[tot++]=i;
mu[i]=-;
}
for(int j=;j<tot&&i*prime[j]<=N;j++){
prime[i*prime[j]]=;
if(i%prime[j]==){
mu[i*prime[j]]=;
break;
}
mu[i*prime[j]]=-mu[i];
}
}
}
ll solve(ll a,ll b){
ll res=;
for(ll l=,r;l<=a;l=r+){
r=min(a/(a/l),b/(b/l));
ll x=(sum[(int)sqrt(r)]-sum[(int)sqrt(l-)]+mod)%mod,y=(a/l)%mod,z=(b/l)%mod;
res=(res+x*y%mod*z%mod)%mod;
}
return res;
}
int main(){
scanf("%lld%lld",&n,&m);
if(n>m) swap(n,m);
getMobius(1e7);
sum[]=;
for(int i=;i<=1e7;i++) sum[i]=sum[i-]+mu[i];
printf("%lld\n",solve(n,m));
return ;
}
Loj #528. 「LibreOJ β Round #4」求和 (莫比乌斯反演)的更多相关文章
-
loj#528. 「LibreOJ β Round #4」求和
求:\(\sum_{i=1}^n\sum_{j=1}^m\mu(gcd(i,j))^2\) 化简可得\(\sum_{i=1}^{min(n,m)}{\lfloor \frac{n}{i} \rfloo ...
-
LibreOJ #528. 「LibreOJ β Round #4」求和
二次联通门 : LibreOJ #528. 「LibreOJ β Round #4」求和 /* LibreOJ #528. 「LibreOJ β Round #4」求和 题目要求的是有多少对数满足他们 ...
-
[LOJ#531]「LibreOJ β Round #5」游戏
[LOJ#531]「LibreOJ β Round #5」游戏 试题描述 LCR 三分钟就解决了问题,她自信地输入了结果-- > -- 正在检查程序 -- > -- 检查通过,正在评估智商 ...
-
[LOJ#530]「LibreOJ β Round #5」最小倍数
[LOJ#530]「LibreOJ β Round #5」最小倍数 试题描述 第二天,LCR 终于启动了备份存储器,准备上传数据时,却没有找到熟悉的文件资源,取而代之的是而屏幕上显示的一段话: 您的文 ...
-
[LOJ#516]「LibreOJ β Round #2」DP 一般看规律
[LOJ#516]「LibreOJ β Round #2」DP 一般看规律 试题描述 给定一个长度为 \(n\) 的序列 \(a\),一共有 \(m\) 个操作. 每次操作的内容为:给定 \(x,y\ ...
-
[LOJ#515]「LibreOJ β Round #2」贪心只能过样例
[LOJ#515]「LibreOJ β Round #2」贪心只能过样例 试题描述 一共有 \(n\) 个数,第 \(i\) 个数 \(x_i\) 可以取 \([a_i , b_i]\) 中任意值. ...
-
[LOJ#525]「LibreOJ β Round #4」多项式
[LOJ#525]「LibreOJ β Round #4」多项式 试题描述 给定一个正整数 k,你需要寻找一个系数均为 0 到 k−1 之间的非零多项式 f(x),满足对于任意整数 x 均有 f(x) ...
-
[LOJ#526]「LibreOJ β Round #4」子集
[LOJ#526]「LibreOJ β Round #4」子集 试题描述 qmqmqm有一个长为 n 的数列 a1,a2,……,an,你需要选择集合{1,2,……,n}的一个子集,使得这个子集中任意两 ...
-
[LOJ#522]「LibreOJ β Round #3」绯色 IOI(危机)
[LOJ#522]「LibreOJ β Round #3」绯色 IOI(危机) 试题描述 IOI 的比赛开始了.Jsp 和 Rlc 坐在一个角落,这时他们听到了一个异样的声音 …… 接着他们发现自己收 ...
随机推荐
-
Thinkphp 中 distinct 的用法
TP中distinct()的用处主要是去除重复的值 在Thinkphp手册中也详细说明了(链接:http://document.thinkphp.cn/manual_3_2.html#distinct ...
-
easyUI 操作
<a href="javascript:void(0)" onclick="locationUrl()">点击 自动加链接</a> fu ...
-
python--数据清洗
1.数据错误: 错误类型– 脏数据或错误数据• 比如, Age = -2003– 数据不正确• '0' 代表真实的0,还是代表缺失– 数据不一致• 比如收入单位是万元,利润单位是元,或者一个单位是美元 ...
-
Solr使用solr4J操作索引库
Solrj是Solr搜索服务器的一个比较基础的客户端工具,可以非常方便地与Solr搜索服务器进行交互.最基本的功能就是管理Solr索引,包括添加.更新.删除和查询等.对于一些比较基础的应用,用Solj ...
-
elaserch 查看节点是否是master
http://192.168.32.81:9200/_cat/nodes 192.168.32.81 192.168.32.81 3 21 0.00 d * node02 192.168.32.80 ...
-
ARM处理器工作模式
学习ARM处理器参考的首选资料是ARM Architecture Reference Manual,是最专业权威的学习资料. ARM处理器共有7种工作模式,如表1-1和1-2所示: 表1-1 处理器工 ...
-
python scrapy 抓取脚本之家文章(scrapy 入门使用简介)
老早之前就听说过python的scrapy.这是一个分布式爬虫的框架,可以让你轻松写出高性能的分布式异步爬虫.使用框架的最大好处当然就是不同重复造*了,因为有很多东西框架当中都有了,直接拿过来使用就 ...
-
python generator(生成器)
a=(x*2 for x in range(1000)) # print(a.next())#python2使用 print(a.__next__()) #python3使用 print(next(a ...
-
APICloud ajpush(极光推送) 6009
APICloud 其它的都按照APICloud的使用说明操作即可,但有一点需要提醒像我一样才接触的朋友:极光推送需打包测试,不能直接自定义Loader.否则,你会发现在绑定别名的方法时会一直返回&qu ...
-
您真的会修改Active Directory域控制器计算机名称吗
从我开始做微软这行开始,就经常听说某某公司由于什么原因需要修改Active Directory域控制器计算机名称,但发现好多公司都是直接修改,导致了各种奇葩的问题,今天就给大家推荐一个修改Active ...