Loj #528. 「LibreOJ β Round #4」求和 (莫比乌斯反演)

时间:2021-09-22 20:24:39

题目链接:https://loj.ac/problem/528

题目:给定两个正整数N,M,你需要计算ΣΣu(gcd(i,j))^2 mod 998244353 ,其中i属于[1,N],j属于[1,M]

解题思路:

Loj #528. 「LibreOJ β Round #4」求和 (莫比乌斯反演)

代码:

#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」求和 (莫比乌斯反演)的更多相关文章

  1. loj&num;528&period; 「LibreOJ β Round &num;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 ...

  2. LibreOJ &num;528&period; 「LibreOJ β Round &num;4」求和

    二次联通门 : LibreOJ #528. 「LibreOJ β Round #4」求和 /* LibreOJ #528. 「LibreOJ β Round #4」求和 题目要求的是有多少对数满足他们 ...

  3. &lbrack;LOJ&num;531&rsqb;「LibreOJ β Round &num;5」游戏

    [LOJ#531]「LibreOJ β Round #5」游戏 试题描述 LCR 三分钟就解决了问题,她自信地输入了结果-- > -- 正在检查程序 -- > -- 检查通过,正在评估智商 ...

  4. &lbrack;LOJ&num;530&rsqb;「LibreOJ β Round &num;5」最小倍数

    [LOJ#530]「LibreOJ β Round #5」最小倍数 试题描述 第二天,LCR 终于启动了备份存储器,准备上传数据时,却没有找到熟悉的文件资源,取而代之的是而屏幕上显示的一段话: 您的文 ...

  5. &lbrack;LOJ&num;516&rsqb;「LibreOJ β Round &num;2」DP 一般看规律

    [LOJ#516]「LibreOJ β Round #2」DP 一般看规律 试题描述 给定一个长度为 \(n\) 的序列 \(a\),一共有 \(m\) 个操作. 每次操作的内容为:给定 \(x,y\ ...

  6. &lbrack;LOJ&num;515&rsqb;「LibreOJ β Round &num;2」贪心只能过样例

    [LOJ#515]「LibreOJ β Round #2」贪心只能过样例 试题描述 一共有 \(n\) 个数,第 \(i\) 个数 \(x_i\) 可以取 \([a_i , b_i]\) 中任意值. ...

  7. &lbrack;LOJ&num;525&rsqb;「LibreOJ β Round &num;4」多项式

    [LOJ#525]「LibreOJ β Round #4」多项式 试题描述 给定一个正整数 k,你需要寻找一个系数均为 0 到 k−1 之间的非零多项式 f(x),满足对于任意整数 x 均有 f(x) ...

  8. &lbrack;LOJ&num;526&rsqb;「LibreOJ β Round &num;4」子集

    [LOJ#526]「LibreOJ β Round #4」子集 试题描述 qmqmqm有一个长为 n 的数列 a1,a2,……,an,你需要选择集合{1,2,……,n}的一个子集,使得这个子集中任意两 ...

  9. &lbrack;LOJ&num;522&rsqb;「LibreOJ β Round &num;3」绯色 IOI(危机)

    [LOJ#522]「LibreOJ β Round #3」绯色 IOI(危机) 试题描述 IOI 的比赛开始了.Jsp 和 Rlc 坐在一个角落,这时他们听到了一个异样的声音 …… 接着他们发现自己收 ...

随机推荐

  1. Thinkphp 中 distinct 的用法

    TP中distinct()的用处主要是去除重复的值 在Thinkphp手册中也详细说明了(链接:http://document.thinkphp.cn/manual_3_2.html#distinct ...

  2. easyUI 操作

    <a href="javascript:void(0)" onclick="locationUrl()">点击 自动加链接</a> fu ...

  3. python--数据清洗

    1.数据错误: 错误类型– 脏数据或错误数据• 比如, Age = -2003– 数据不正确• '0' 代表真实的0,还是代表缺失– 数据不一致• 比如收入单位是万元,利润单位是元,或者一个单位是美元 ...

  4. Solr使用solr4J操作索引库

    Solrj是Solr搜索服务器的一个比较基础的客户端工具,可以非常方便地与Solr搜索服务器进行交互.最基本的功能就是管理Solr索引,包括添加.更新.删除和查询等.对于一些比较基础的应用,用Solj ...

  5. 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 ...

  6. ARM处理器工作模式

    学习ARM处理器参考的首选资料是ARM Architecture Reference Manual,是最专业权威的学习资料. ARM处理器共有7种工作模式,如表1-1和1-2所示: 表1-1 处理器工 ...

  7. python scrapy 抓取脚本之家文章&lpar;scrapy 入门使用简介&rpar;

    老早之前就听说过python的scrapy.这是一个分布式爬虫的框架,可以让你轻松写出高性能的分布式异步爬虫.使用框架的最大好处当然就是不同重复造*了,因为有很多东西框架当中都有了,直接拿过来使用就 ...

  8. python generator&lpar;生成器&rpar;

    a=(x*2 for x in range(1000)) # print(a.next())#python2使用 print(a.__next__()) #python3使用 print(next(a ...

  9. APICloud ajpush&lpar;极光推送&rpar; 6009

    APICloud 其它的都按照APICloud的使用说明操作即可,但有一点需要提醒像我一样才接触的朋友:极光推送需打包测试,不能直接自定义Loader.否则,你会发现在绑定别名的方法时会一直返回&qu ...

  10. 您真的会修改Active Directory域控制器计算机名称吗

    从我开始做微软这行开始,就经常听说某某公司由于什么原因需要修改Active Directory域控制器计算机名称,但发现好多公司都是直接修改,导致了各种奇葩的问题,今天就给大家推荐一个修改Active ...