bzoj2154||洛谷P1829 Crash的数字表格&&JZPTAB && bzoj3309 DZY Loves Math

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

bzoj2154||洛谷P1829

https://www.lydsy.com/JudgeOnline/problem.php?id=2154

https://www.luogu.org/problemnew/show/P1829

不妨设n<=m

就是求$ans=\sum_{k=1}^m{\frac{1}{k}}\sum_{i=1}^n\sum_{j=1}^m{ij[(i,j)=k]}$

把1/k后面的那一部分提出来，设为f(k)，

然后莫比乌斯反演得到f(k)较简易的计算式，代回ans，并化简（过程略）

最后化简出来是$\sum_{k=1}^m{k}\sum_{i=1}^{{\lfloor}\frac{m}{k}{\rfloor}}\mu(i){i^2}g({{\lfloor}\frac{{\lfloor}\frac{n}{k}{\rfloor}}{i}{\rfloor}},{{\lfloor}\frac{{\lfloor}\frac{m}{k}{\rfloor}}{i}{\rfloor}})$

其中$g(x,y)=\frac{(x+1)x(y+1)y}{4}$

可以通过两重的整除分块以O(n)的复杂度计算（第一重枚举n/k,m/k，第二重枚举(n/k)/i,(m/k)/i）

额，好像还有一道题面基本一样的题（然而bzoj权限题，不能交），然而是很多组数据，不能每次O(n)算

相关：https://blog.csdn.net/qq_30974369/article/details/79087445

对于这个式子$\sum_{k=1}^m{k}\sum_{i=1}^{{\lfloor}\frac{m}{k}{\rfloor}}\mu(i){i^2}g({{\lfloor}\frac{n}{ik}{\rfloor}},{{\lfloor}\frac{m}{ik}{\rfloor}})$

令T=ik

原式=$\sum_{k=1}^m{k}\sum_{k|T}\mu(\frac{T}{k})(\frac{T}{k})^2g({{\lfloor}\frac{n}{T}{\rfloor}},{{\lfloor}\frac{m}{T}{\rfloor}})$

=$\sum_{T=1}^mg({{\lfloor}\frac{n}{T}{\rfloor}},{{\lfloor}\frac{m}{T}{\rfloor}})\sum_{k|T}k\mu(\frac{T}{k})(\frac{T}{k})^2$

最后从sigma k|T开始那一部分，等于$(id*(\mu\cdot id\cdot id))(T)$

是个积性函数，且是可以线性筛出来的（然而我不会，又去查了题解），将其设为函数h

对于1，h[1]=1

对于一个质数p，h[p]=$1*\mu(p)*p^2+p*\mu(1)*1^2$

对于i%p!=0，h(i*p)=h(i)*h(p)（由于积性）

对于i%p==0，由于h(i*p)拆开后式子中比h(i)多的项的$\mu$值均为0，因此只有对于h(i)中已有的项增加贡献；每一项由$\mu(d)*d^2*(i/d)$变到$\mu(d)*d^2*((i*p)/d)$，因此h(i*p)=h(i)*p

筛出来之后做一下前缀和，这样子每一次询问就可以数论分块根号解决了

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
#define md 20101009
#define N 10000000
ll prime[N+],len,dd[N+];
bool nprime[N+];
ll h[N+];
ll Mod(ll a,ll b)
{
if(a>=) return a%b;
else if(a%b==) return ;
else return b+a%b;
}
ll G(ll x,ll y)
{
return (x+)*x%md*(y+)%md*y%md*%md;
}
ll n,m;
int main()
{
ll i,j,ans=;
h[]=;
for(i=;i<=N;i++)
{
if(!nprime[i]) prime[++len]=i,h[i]=Mod(-i*i+i,md);
for(j=;j<=len&&i*prime[j]<=N;j++)
{
nprime[i*prime[j]]=;
if(i%prime[j]==) {h[i*prime[j]]=h[i]*prime[j]%md;break;}
else h[i*prime[j]]=h[i]*h[prime[j]]%md;
}
}
for(i=;i<=N;i++) dd[i]=(dd[i-]+h[i])%md;
scanf("%lld%lld",&n,&m);
//n=10000000;m=1000;
if(n>m) swap(n,m);
for(i=;i<=m;i=j+)
{
if(n<i) j=min(m,m/(m/i));
else j=min(m,min(n/(n/i),m/(m/i)));
ans=(ans+Mod(dd[j]-dd[i-],md)*G(n/i,m/i))%md;
}
printf("%lld",ans);
return ;
}

upd181010:

$\sum_{k|T}k\mu(\frac{T}{k})(\frac{T}{k})^2=T\sum_{k|T}\mu(\frac{T}{k})\frac{T}{k}=T\sum_{k|T}\mu(k)k$

这个式子似乎并没有什么用...但是可以记一下，说不定下次就给出最后的那个呢

bzoj3309

https://www.lydsy.com/JudgeOnline/problem.php?id=3309

不妨设a<=b

显然原式=$\sum_{k=1}^bf(k)\sum_{i=1}^{{\lfloor}\frac{b}{k}{\rfloor}}\mu(i){{\lfloor}\frac{a}{ik}{\rfloor}}{{\lfloor}\frac{b}{ik}{\rfloor}}$

用跟上面类似的方法变到$\sum_{T=1}^b{\lfloor}\frac{a}{T}{\rfloor}{\lfloor}\frac{b}{T}{\rfloor}\sum_{k|T}f(k)\mu(\frac{T}{k})$

后面那个不太好筛啊，根本就不会，我又去查题解了。。。

（弃用）如果i%p==0，可以丢掉那些新产生因子的$\mu$，每一项是由$\mu(d)f(i/d)$变到$\mu(d)f(i/d*p)$，显然会加(i的(i/d)中"最大幂指数等于最小质因子的幂指数"的数的$\mu(d)$之和)，那个求时依赖的值也可以递推出

（弃用）如果i%p!=0，那么首先会多一些产生贡献的项，这些项是由原来i的任意因子乘上一个p得到的，是$\mu(i/d)f(d)$变到$\mu(i*p/(d*p))f(d*p)=\mu(i/d)f(dp)$，产生的贡献是原来的总和加上一个值（i的因子中"最大幂指数等于最小质因子的幂指数"的数(设为d)的$\mu(i/d)$之和）；

筛法的解释：https://blog.csdn.net/phenix_2015/article/details/50799021

这条结论，简单来讲，就是那个函数，只有各个质因子的指数相等的有值((-1)^{质因子数+1})，其他都为0

直接想好像很难想到的样子。。以后记得做这类题要打打表分解分解质因数找找规律

算是A了吧。。。

#pragma GCC optimize(3)
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
#define N 10000000
ll prime[N+],len,mu[N+];
ll n1[N+],n2[N+],n3[N+],h[N+];
//分别为最小质因子次数，其他质因子次数，质因子数，函数值
//n2为-1:第一个质因子;n2为-2:已经失败
bool nprime[N+];
ll a,b,ans,T;
template<class T>
inline void read(T &x) {
int f=;x=;char ch=getchar();
while(ch>''||ch<''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x*=;x+=(ch-'');ch=getchar();}
x*=f;
}
template<class T>
inline void write(T x) {
if(x<) putchar('-'),x=-x;
if(x>) write(x/);
putchar(x%+'');
}
int main()
{
ll i,j;
mu[]=;
for(i=;i<=N;i++)
{
if(!nprime[i])
{
prime[++len]=i;
mu[i]=-;
n2[i]=-;
n3[i]=;
n1[i]=;
h[i]=;
}
for(j=;j<=len&&i*prime[j]<=N;j++)
{
nprime[i*prime[j]]=;
if(i%prime[j]==)
{
mu[i*prime[j]]=;
n1[i*prime[j]]=n1[i]+;
n2[i*prime[j]]=n2[i];
n3[i*prime[j]]=n3[i];
if(n2[i*prime[j]]==-||n1[i*prime[j]]==n2[i*prime[j]])
h[i*prime[j]]=(n3[i*prime[j]]%==)?-:;
else
h[i*prime[j]]=;
break;
}
else
{
mu[i*prime[j]]=-mu[i];
n1[i*prime[j]]=;
n2[i*prime[j]]=(n2[i]==-||n2[i]==n1[i])?n1[i]:-;
n3[i*prime[j]]=n3[i]+;
if(n2[i*prime[j]]==-||n1[i*prime[j]]==n2[i*prime[j]])
h[i*prime[j]]=(n3[i*prime[j]]%==)?-:;
else
h[i*prime[j]]=;
}
}
}
//for(i=1;i<=1000;i++) printf("%lld %lld %lld %lld\n",i,h[i],n1[i],n2[i]);
//return 0;
for(i=;i<=N;i++) h[i]+=h[i-];
read(T);
//T=1000;
while(T--)
{
read(a);read(b);
//a=7558588;b=9653114;
if(a==||b==)
{
puts("");
continue;
}
if(a>b) swap(a,b);
ans=;
for(i=;i<=a;i=j+)
{
j=min(a/(a/i),b/(b/i));
ans+=(a/i)*(b/i)*(h[j]-h[i-]);
}
write(ans);putchar('\n');
}
return ;
}

bzoj2154||洛谷P1829 Crash的数字表格&&JZPTAB && bzoj3309 DZY Loves Math的更多相关文章

洛谷 - P1829 - Crash的数字表格 - 莫比乌斯反演
求: $S(n,m)=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}lcm(i,j)$ 显然: \(S(n,m)=\sum\limits_{i=1}^{n}\ ...
洛谷 P1829 [国家集训队]Crash的数字表格 / JZPTAB 解题报告
[国家集训队]Crash的数字表格 / JZPTAB 题意求$\sum\limits_{i=1}^n\sum\limits_{j=1}^mlcm(i,j)$,$n,m\le 10^7$ 鉴于 ...
[Luogu P1829] [国家集训队]Crash的数字表格 / JZPTAB (莫比乌斯反演)
题面传送门:洛咕 Solution 调到自闭,我好菜啊为了方便讨论,以下式子$m>=n$ 为了方便书写,以下式子中的除号均为向下取整我们来颓柿子吧qwq 显然,题目让我们求: \(\l ...
题解-[国家集训队]Crash的数字表格 / JZPTAB
题解-[国家集训队]Crash的数字表格 / JZPTAB 前置知识: 莫比乌斯反演 </> [国家集训队]Crash的数字表格 / JZPTAB 单组测试数据,给定 $n,m$ ,求 ...
[luogu1829][bzoj2154][国家集训队]Crash的数字表格 / JZPTAB【莫比乌斯反演】
传送门:洛谷,bzoj 题目描述今天的数学课上,Crash小朋友学习了最小公倍数(Least Common Multiple).对于两个正整数a和b,LCM(a, b)表示能同时整除a和b的最小正整 ...
洛谷P1829 [国家集训队]Crash的数字表格 / JZPTAB(莫比乌斯反演)
题目背景提示:原 P1829 半数集问题已经迁移至 P1028 数的计算题目描述今天的数学课上,Crash小朋友学习了最小公倍数(Least Common Multiple).对于两个正整数a ...
洛谷P1829 [国家集训队]Crash的数字表格 / JZPTAB（莫比乌斯反演）
传送门式子好麻烦orz……大佬好腻害orz->这里 //minamoto #include<iostream> #include<cstdio> #define ll ...
洛谷 P1829 [国家集训队]Crash的数字表格 / JZPTAB（莫比乌斯反演）
题意:求$\sum_{i=1}^{n}\sum_{j=1}^{m}lcm(i,j)$. 开始开心(自闭)化简: $\sum_{i=1}^{n}\sum_{j=1}^{m}lcm(i,j)$ =$\su ...
P1829 [国家集训队]Crash的数字表格 / JZPTAB
推式子太快乐啦!虽然我好蠢而且dummy和maomao好巨(划掉) 思路莫比乌斯反演的题目首先这题有$O(\sqrt n)$的做法但是我没写咕咕咕然后就是爆推一波式子 \[ \sum_{i= ...

随机推荐

【BZOJ-2179&amp&semi;2194】FFT快速傅里叶&amp&semi;快速傅里叶之二 FFT
2179: FFT快速傅立叶 Time Limit: 10 Sec Memory Limit: 259 MBSubmit: 2978 Solved: 1523[Submit][Status][Di ...
RunTimeException包括：
大约有如下几种: NullPointerException - 空指针引用异常 ClassCastException - 类型强制转换异常 IllegalArgumentException- 传递非法 ...
319&period; Bulb Switche
There are n bulbs that are initially off. You first turn on all the bulbs. Then, you turn off every ...
good bye 2015 B - New Year and Old Property
题意:统计在n,m之间的数的二进制表示形式只有一个零的数目. 位运算模拟+dfs #include<iostream> #include<string> #include&lt ...
SCALA中的函数式编程
演示了值函数,匿名函数,闭包... 其它具体的应用,还得在生产当中吧.. 这个告一段落..其它SAM,CURRY,高阶函数,集合,泛型,隐式类..这些,还是找专门的书去深入了解啦... C:\User ...
OpenCV 之网络摄像头
1 RTSP RTSP (Real Time Streaming Protocol),是一种语法和操作类似 HTTP 协议,专门用于音频和视频的应用层协议. 和 HTTP 类似,RTSP 也使用 ...
C&num;SMTP发邮件
public static bool SendMailUse() { string host = "smtp.163.com";// 邮件服务器smtp.163.com表示网易邮箱 ...
Tempset 暴风射击
发售年份 1980 平台街机开发商雅达利(Atari) 类型射击 https://www.youtube.com/watch?v=AMto2HJJSSA
JS 的execCommand 方法做的一个简单富文本
execCommand 当一个 HTML 文档切换到设计模式(designMode)时,文档对象暴露 execCommand 方法,该方法允许运行命令来操纵可编辑区域的内容.大多数命令影响文档的选择( ...
springboot - Constructor、&commat;Autowired、&commat;PostConstruct分析
1.Constructor 构造方法 2.@Autowired 依赖注入 3.@PostConstruct 在依赖注入完成后被自动调用 4. 三者的顺序: 从依赖注入的字面意思就可以知道,要将对象p注 ...