【bzoj2154】【Crash的数字表格】【莫比乌斯反演】
发布日期:2021-11-16 15:38:12
浏览次数:9
分类:技术文章
本文共 1395 字,大约阅读时间需要 4 分钟。
Description
今天的数学课上,Crash小朋友学习了最小公倍数(Least Common Multiple)。对于两个正整数a和b,LCM(a, b)表示能同时被a和b整除的最小正整数。例如,LCM(6, 8) = 24。回到家后,Crash还在想着课上学的东西,为了研究最小公倍数,他画了一张N*M的表格。每个格子里写了一个数字,其中第i行第j列的那个格子里写着数为LCM(i, j)。一个4*5的表格如下: 1 2 3 4 5 2 2 6 4 10 3 6 3 12 15 4 4 12 4 20 看着这个表格,Crash想到了很多可以思考的问题。不过他最想解决的问题却是一个十分简单的问题:这个表格中所有数的和是多少。当N和M很大时,Crash就束手无策了,因此他找到了聪明的你用程序帮他解决这个问题。由于最终结果可能会很大,Crash只想知道表格里所有数的和mod 20101009的值。 Input 输入的第一行包含两个正整数,分别表示N和M。 Output 输出一个正整数,表示表格中所有数的和mod 20101009的值。 Sample Input 4 5 Sample Output 122 【数据规模和约定】 100%的数据满足N,M≤ 107. 题解: 同bzoj2693,还是单组询问。#include#include #include #define N 10000010#define P 20101009#define LL long longusing namespace std;int p[N],f[N],n,m,T,pos;LL g[N],ans,s[N];void pre(){ g[1]=1; for (int i=2;i<=n;i++){ if (!f[i]){p[++p[0]]=i;g[i]=(1-i+P)%P;} for (int j=1;j<=p[0]&&i*p[j]<=n;j++){ f[i*p[j]]=1; if (i%p[j]==0){g[i*p[j]]=g[i];break;} g[i*p[j]]=(g[i]*g[p[j]])%P; } } for (int i=1;i<=n;i++) g[i]=(g[i]*i)%P; for (int i=1;i<=n;i++) s[i]=(s[i-1]+g[i])%P;}LL sum(LL x,LL y){ LL t1=x*(x+1)/2;LL t2=y*(y+1)/2; t1%=P;t2%=P; return (t1*t2)%P; }int main(){ scanf("%d%d",&n,&m);pre(); if (n>m) swap(n,m);ans=0;pos=0; for (int i=1;i<=n;i=pos+1){ pos=min((n/(n/i)),(m/(m/i))); ans+=(sum((LL)(n/i),(LL)(m/i))*(s[pos]-s[i-1]+P)%P)%P; ans%=P; } printf("%lld",ans); }
转载地址:https://blog.csdn.net/sunshinezff/article/details/50952660 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
逛到本站,mark一下
[***.202.152.39]2024年04月14日 08时51分52秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
将《 两周自制脚本语言 》测试中使用的接口中文化
2019-04-26
5分钟入门LingaScript-尝鲜中文版TypeScript
2019-04-26
重拾《 两周自制脚本语言 》- 支持中文标识符
2019-04-26
Java实现文本编辑时基于拼音输入的补全原型
2019-04-26
从立创EDA,Gratipay看中文编程开发环境和推广运营的一个趋势
2019-04-26
中文代码之Django官方入门:建立模型
2019-04-26
Python实现推流直播
2019-04-26
你不得不了解的卷积神经网络发展史
2019-04-26
你不得不了解的机器学习知识
2019-04-26
你不得不了解的深度学习知识(一)
2019-04-26
你不得不了解的深度学习知识(二)
2019-04-26
AI算法之Encoder-Decoder 和 Seq2Seq
2019-04-26
AI算法之Attention机制
2019-04-26
人体口罩佩戴检测实战
2019-04-26
[实战]200类鸟类细粒度图像分类
2019-04-26
【实战】英文垃圾短信分类
2019-04-26
FFmpeg初遇见_基本命令
2019-04-26
Urbansound8k声音分类深度学习实战
2019-04-26