首页 > 其他分享 >SP8099 TABLE - Crash´s number table 题解

SP8099 TABLE - Crash´s number table 题解

时间:2024-07-30 20:08:45浏览次数:16  
标签:lfloor right frac limits 题解 sum rfloor SP8099 Crash

题目传送门

前置知识

一般的积性函数 | 数论分块 | 莫比乌斯反演

解法

令 \(n \le m\)。

考虑莫比乌斯反演,推式子,有 \(\begin{aligned} &\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\operatorname{lcm}(i,j) \\ &=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\frac{ij}{\gcd(i,j)} \\ &=\sum\limits_{k=1}^{n}\frac{1}{k}\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}ij[\gcd(i,j)=k] \\ &=\sum\limits_{k=1}^{n}\frac{1}{k}\sum\limits_{i=1}^{\left\lfloor \frac{n}{k} \right\rfloor}\sum\limits_{j=1}^{\left\lfloor \frac{m}{k} \right\rfloor}ijk^{2}[\gcd(i,j)=1] \\ &=\sum\limits_{k=1}^{n}k\sum\limits_{i=1}^{\left\lfloor \frac{n}{k} \right\rfloor}\sum\limits_{j=1}^{\left\lfloor \frac{m}{k} \right\rfloor}ij\sum\limits_{d|\gcd(i,j)}\mu(d) \\ &=\sum\limits_{k=1}^{n}k\sum\limits_{d=1}^{n}\mu(d)\sum\limits_{i=1}^{\left\lfloor \frac{n}{k} \right\rfloor}\sum\limits_{j=1}^{\left\lfloor \frac{m}{k} \right\rfloor}ij[d|\gcd(i,j)] \\ &=\sum\limits_{k=1}^{n}k\sum\limits_{d=1}^{n}\mu(d)d^{2}\sum\limits_{i=1}^{\left\lfloor \frac{n}{kd} \right\rfloor}\sum\limits_{j=1}^{\left\lfloor \frac{m}{kd} \right\rfloor}ij \\ &=\sum\limits_{k=1}^{n}k\sum\limits_{d=1}^{n}\mu(d)d^{2}\sum\limits_{i=1}^{\left\lfloor \frac{n}{kd} \right\rfloor}i\sum\limits_{j=1}^{\left\lfloor \frac{m}{kd} \right\rfloor}j \\ &=\sum\limits_{T=1}^{n}T\sum\limits_{d|T}\mu(d)d\sum\limits_{i=1}^{\left\lfloor \frac{n}{T} \right\rfloor}i\sum\limits_{j=1}^{\left\lfloor \frac{m}{T} \right\rfloor}j \end{aligned}\)。

\(f(n)=\sum\limits_{d|n}\mu(d)d\) 显然是积性函数,线筛筛一下即可。

接着维护前缀和后整除分块。

需要注意的是本题仅限 C++98 提交。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define ull unsigned long long
#define sort stable_sort 
#define endl '\n'
const ll p=20101009;
ll prime[10000010],vis[10000010],miu[10000010],f[10000010],sum[10000010],s[10000010],len=0;
void isprime(ll n)
{
	memset(vis,0,sizeof(vis));
	miu[1]=1;
	f[1]=1;
	for(ll i=2;i<=n;i++)
	{
		if(vis[i]==0)
		{
			len++;
			prime[len]=i;
			miu[i]=-1;
			f[i]=1-i;
		}
		for(ll j=1;j<=len&&i*prime[j]<=n;j++)
		{
			vis[i*prime[j]]=1;
			if(i%prime[j]==0)
			{
				miu[i*prime[j]]=0;
				f[i*prime[j]]=f[i];
				break;
			}
			else
			{
				miu[i*prime[j]]=-miu[i];
				f[i*prime[j]]=f[i]*f[prime[j]];
			}
		}
	}
	for(ll i=1;i<=n;i++)
	{
		s[i]=(s[i-1]+i)%p;
		sum[i]=(sum[i-1]+f[i]*i%p+p)%p;
	}
}
ll ask(ll n,ll m)
{
	ll ans=0,l,r;
	for(l=1,r;l<=n;l=r+1)
	{
		r=min(n/(n/l),m/(m/l));
		ans=(ans+(s[n/l]*s[m/l]%p)*(sum[r]-sum[l-1]+p)%p)%p;
	}
	return ans;
}
int main()
{
	ll n,m;
	cin>>n>>m;
	isprime(max(n,m));
	if(n>m)
	{
		swap(n,m);
	}
	cout<<ask(n,m)<<endl;
	return 0;
}

后记

多倍经验:luogu P1829 [国家集训队] Crash的数字表格 / JZPTAB

标签:lfloor,right,frac,limits,题解,sum,rfloor,SP8099,Crash
From: https://www.cnblogs.com/The-Shadow-Dragon/p/18333249

相关文章

  • 题解:Pinely Round 4 (Div. 1 + Div. 2) A
    A.MaximizetheLastElementtimelimitpertest:1secondmemorylimitpertest:256megabytesinput:standardinputoutput:standardoutputYouaregivenanarray\(a\)of\(n\)integers,where\(n\)isodd.Inoneoperation,youwillremovetwoa......
  • P4449 于神之怒加强版 (题解)
    题目链接P4449于神之怒加强版题目大意:求\[\sum_{i=1}^{n}\sum_{j=1}^{m}gcd(i,j)^k\]\(数据范围n,m\leq5e6\)\(二话不说,先开导式子(假定n<m):\)\begin{aligned}ans&=\sum_{i=1}^{n}\sum_{j=1}^{m}gcd(i,j)^k\\\end{aligned}\[先套路地枚举d=gcd(i,j)\]\begin{align......
  • 题解 - Alice
    题目描述Alice和Bob在玩游戏,游戏规则如下:有两堆石子,每堆石子有非负整数个Alice与Bob轮流操作,Alice先手,每次可以从任意一堆石子中取出若干个取出的石子个数应满足为另一堆石子个数的因数(此处规定任何数均为0的因数)将石子取完的玩家获胜给定一个初始状态,现......
  • [POI2007] OSI-Axes of Symmetry 题解
    给出一个多边形,求对称轴数量。考虑对于一个多边形,其是对称的当且仅当对于若干个边(角),其左右的角与边都是对称的。考虑如果我们对于内角构造出一种单射,映射为一个整数,将边映射为它的边长,那么我们按照角,边,角,边,……的顺序将他们加入数组中,能构造出一个长度为\(2n\)的数组,将这个......
  • 旅行 题解
    题目id:20300题目描述鱼大大计划环华夏自驾游游玩一圈,在他的计划中,这次旅行将在\(m\)天内完成,预计游玩\(n\)个城市,每个城市游玩\(x\)天,然后赶路开车以均速去到下一个城市,现鱼大大从海洋城市出发,按游玩顺序先后给出每个城市和上一个城市之间的距离(\(km\)),问鱼大大每天至少赶路多......
  • 质数差列 题解
    题目id:20315题目描述驰骋宇宙的鱼大大找到了一个古遗迹,稍作研究后发现这是一个来着远古的质数星球文明遗迹,这个文明的特点是所有事物都和质数息息相关。于是,鱼大大赶紧列出了一堆的质数,以方便自己的研究。这天鱼大大找到了质数星球文明的一个遗迹仓库大门,正准备破解密码的同时......
  • [POI2008] POC-Trains 题解
    前言题目链接:洛谷。时间复杂度和输入同阶的做法。题意简述有\(n\)(\(n\leq10^3\))个长\(m\)的字符串,\(q\)(\(q\leq10^5\))次操作,交换两个字符串的两个字符。问每个字符串在所有时刻,最多有几个和它相等。题目分析套路做法看到字符串相等,想到使用哈希。但是要支持修改,怎么......
  • 题解:[ABC363D] Palindromic Number
    提示特定位数的回文数数量是可以快速计算出来的,对于特定的位数\(n\),第一位由于不能有前导\(0\),共有\(9\)种选择,而从第\(2\)位到第\(\frac{n+1}{2}\)位都有\(10\)种选择(一个回文数完全由它的前半部分确定)。所以\(n\)位数中共有\(S(n)=9*10^\frac{n-1}{2}......
  • Crash Course Computer Science
    【计算机科学速成课】[40集全/精校]-CrashCourseComputerScienceep1.EarlyComputingCharlesBabbageEnglishmathematicianandinventorconceivedthefirstautomaticdigitalcomputerAdaLovelaceEnglishmathematicianthefirstcomputerprogramme......
  • P3811 【模板】模意义下的乘法逆元 题解
    【模板】模意义下的乘法逆元题目背景这是一道模板题题目描述给定n,pn,pn,p求......