数论风骚套路汇总(不定期更新)

2024-02-04 11:48

本文主要是介绍数论风骚套路汇总(不定期更新),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

          • 10.30日更新(多项莫比乌斯反演)
          • 10.31日更新

数论这个东西,确实值得深刻的研究。这里专门开一篇博客,记录遇见的一些奇技淫巧,一些妖艳的操作。(不定期更新)


10.30日更新(多项莫比乌斯反演)

∑ i = 1 a 1 ∑ j = 1 a 2 … … ∑ x = 1 a x g c d ( i , j … … , x ) \sum_{i=1}^{a_1}\sum_{j=1}^{a_2}……\sum_{x=1}^{a_x}gcd(i,j……,x) i=1a1j=1a2x=1axgcd(i,j,x)其中循环的 ∑ \sum 最多有10个。

这道题看上去很不可做,但实际上跟BZOJ2005这道题的本质和推法是一样的。
m i n min min a 1 … … a x a_1……a_x a1ax中的最小值

∑ i = 1 a 1 ∑ j = 1 a 2 … … ∑ x = 1 a x g c d ( i , j … … , x ) = = ∑ i = 1 a 1 ∑ j = 1 a 2 … … ∑ x = 1 a x ∑ k = 1 m i n k ∗ [ g c d ( i , j … … , x ) = k ] \sum_{i=1}^{a_1}\sum_{j=1}^{a_2}……\sum_{x=1}^{a_x}gcd(i,j……,x)==\sum_{i=1}^{a_1}\sum_{j=1}^{a_2}……\sum_{x=1}^{a_x}\sum_{k=1}^{min}k*[gcd(i,j……,x)=k] i=1a1j=1a2x=1axgcd(i,j,x)==i=1a1j=1a2x=1axk=1mink[gcd(i,j,x)=k]

= ∑ k = 1 m i n k ∗ ∑ i = 1 a 1 k ∑ j = 1 a 2 k … … ∑ x = 1 a x k [ g c d ( i , j … … , x ) = 1 ] = = ∑ k = 1 m i n k ∗ ∑ i = 1 a 1 k ∑ j = 1 a 2 k … … ∑ x = 1 a x k ∑ x ∣ g c d ( i , j … … , x ) μ ( x ) =\sum_{k=1}^{min}k*\sum_{i=1}^{\frac{a_1}{k}}\sum_{j=1}^{\frac{a_2}{k}}……\sum_{x=1}^{\frac{a_x}{k}}[gcd(i,j……,x)=1]==\sum_{k=1}^{min}k*\sum_{i=1}^{\frac{a_1}{k}}\sum_{j=1}^{\frac{a_2}{k}}……\sum_{x=1}^{\frac{a_x}{k}}\sum_{x|gcd(i,j……,x)}\mu(x) =k=1minki=1ka1j=1ka2x=1kax[gcd(i,j,x)=1]==k=1minki=1ka1j=1ka2x=1kaxxgcd(i,j,x)μ(x)

= ∑ k = 1 m i n k ∗ ∑ x = 1 m i n k μ ( x ) [ a 1 k x ] [ a 2 k x ] … … [ a x k x ] = = ∑ k = 1 m i n k ∗ [ a 1 k ] [ a 2 k ] … … [ a x k ] φ ( k ) =\sum_{k=1}^{min}k*\sum_{x=1}^{\frac{min}{k}}\mu(x)[\frac{a_1}{kx}][\frac{a_2}{kx}]……[\frac{a_x}{kx}]==\sum_{k=1}^{min}k*[\frac{a_1}{k}][\frac{a_2}{k}]……[\frac{a_x}{k}]φ(k) =k=1minkx=1kminμ(x)[kxa1][kxa2][kxax]==k=1mink[ka1][ka2][kax]φ(k)

于是就可以开心的数论分块喽!

#include<bits/stdc++.h>
#define MAXN 1000005
#define inf 2147483647
#define ll long long
using namespace std;
const ll MD=1e9+7;
ll read(){char c;ll x;while(c=getchar(),c<'0'||c>'9');x=c-'0';while(c=getchar(),c>='0'&&c<='9') x=x*10+c-'0';return x;
}
ll T,n,i,s,top,l,r,Min,ans,a[15],vis[MAXN],pri[MAXN],phi[MAXN],sum[MAXN];
void pre(){vis[1]=1;phi[1]=1;sum[1]=1;for(ll i=2;i<=1000000;i++){if(!vis[i]) pri[++top]=i,phi[i]=i-1;for(ll j=1;j<=top&&i*pri[j]<=1000000;j++){vis[i*pri[j]]=1;if(i%pri[j]) phi[i*pri[j]]=phi[i]*phi[pri[j]]%MD;else{phi[i*pri[j]]=phi[i]*pri[j]%MD;break;}}sum[i]=sum[i-1]+phi[i];}
}
int main()
{T=read();pre();while(T--){n=read();l=1;ans=0;Min=2e9;for(ll i=1;i<=n;i++) a[i]=read(),Min=min(Min,a[i]);while(l<=Min){r=inf;s=1;for(ll i=1;i<=n;i++) {r=min(r,a[i]/(a[i]/l));s=(a[i]/l*s)%MD;}(ans+=(sum[r]-sum[l-1]+2*MD)%MD*s%MD)%MD;l=r+1;}printf("%lld\n",ans%MD);}return 0;
}

10.31日更新

f ( x ) = ∑ i = 1 ∞ ∑ j = 1 ∞ [ i ∗ j ∣ x ] f(x)=\sum_{i=1}^{\infty}\sum_{j=1}^{\infty}[i*j|x] f(x)=i=1j=1[ijx],求 ∑ i = 1 n f ( i ) \sum_{i=1}^{n}f(i) i=1nf(i)

这道题的关键点就是转化,我们将条件转化,假设 x i ∗ j = k \frac{x}{i*j}=k ijx=k,那么我们求 f ( x ) f(x) f(x)只要枚举三元组 ( i , j , k ) (i,j,k) (i,j,k)即可。

我们先假设 a ≤ b ≤ c a\leq b\leq c abc,那么我们 a a a 1 1 1 n 3 \sqrt[3]{n} 3n 枚举, b b b a a a x a \sqrt{\frac{x}{a}} ax 枚举,也就是for(ll a=1;a*a*a<=n;a++) for(ll b=a;a*b*b<=n;b++),那

c c c就可以取 [ b , n a ∗ b ] [b,\frac{n}{a*b}] [b,abn],因为这样相乘都 ≤ n \leq n n。于是用方案乘以这三元组倒换顺序的方案数即可。

核心代码,可以证明复杂度是 O ( n 2 3 ) O(n^{\frac{2}{3}}) O(n32),非常优秀。

for(ll a=1;a*a*a<=n;a++)    for(ll b=a;a*b*b<=n;b++){    ll c=n/(a*b);    if(c<b) break;   if(a==b)   ans+=(c-b)*3+1;  else   ans+=(c-b)*6+3; }

这篇关于数论风骚套路汇总(不定期更新)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/677391

相关文章

MySQL追踪数据库表更新操作来源的全面指南

《MySQL追踪数据库表更新操作来源的全面指南》本文将以一个具体问题为例,如何监测哪个IP来源对数据库表statistics_test进行了UPDATE操作,文内探讨了多种方法,并提供了详细的代码... 目录引言1. 为什么需要监控数据库更新操作2. 方法1:启用数据库审计日志(1)mysql/mariad

linux重启命令有哪些? 7个实用的Linux系统重启命令汇总

《linux重启命令有哪些?7个实用的Linux系统重启命令汇总》Linux系统提供了多种重启命令,常用的包括shutdown-r、reboot、init6等,不同命令适用于不同场景,本文将详细... 在管理和维护 linux 服务器时,完成系统更新、故障排查或日常维护后,重启系统往往是必不可少的步骤。本文

Linux实现线程同步的多种方式汇总

《Linux实现线程同步的多种方式汇总》本文详细介绍了Linux下线程同步的多种方法,包括互斥锁、自旋锁、信号量以及它们的使用示例,通过这些同步机制,可以解决线程安全问题,防止资源竞争导致的错误,示例... 目录什么是线程同步?一、互斥锁(单人洗手间规则)适用场景:特点:二、条件变量(咖啡厅取餐系统)工作流

8种快速易用的Python Matplotlib数据可视化方法汇总(附源码)

《8种快速易用的PythonMatplotlib数据可视化方法汇总(附源码)》你是否曾经面对一堆复杂的数据,却不知道如何让它们变得直观易懂?别慌,Python的Matplotlib库是你数据可视化的... 目录引言1. 折线图(Line Plot)——趋势分析2. 柱状图(Bar Chart)——对比分析3

JAVA数组中五种常见排序方法整理汇总

《JAVA数组中五种常见排序方法整理汇总》本文给大家分享五种常用的Java数组排序方法整理,每种方法结合示例代码给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录前言:法一:Arrays.sort()法二:冒泡排序法三:选择排序法四:反转排序法五:直接插入排序前言:几种常用的Java数组排序

Oracle 通过 ROWID 批量更新表的方法

《Oracle通过ROWID批量更新表的方法》在Oracle数据库中,使用ROWID进行批量更新是一种高效的更新方法,因为它直接定位到物理行位置,避免了通过索引查找的开销,下面给大家介绍Orac... 目录oracle 通过 ROWID 批量更新表ROWID 基本概念性能优化建议性能UoTrFPH优化建议注

防止SpringBoot程序崩溃的几种方式汇总

《防止SpringBoot程序崩溃的几种方式汇总》本文总结了8种防止SpringBoot程序崩溃的方法,包括全局异常处理、try-catch、断路器、资源限制、监控、优雅停机、健康检查和数据库连接池配... 目录1. 全局异常处理2. 使用 try-catch 捕获异常3. 使用断路器4. 设置最大内存和线

Redis中6种缓存更新策略详解

《Redis中6种缓存更新策略详解》Redis作为一款高性能的内存数据库,已经成为缓存层的首选解决方案,然而,使用缓存时最大的挑战在于保证缓存数据与底层数据源的一致性,本文将介绍Redis中6种缓存更... 目录引言策略一:Cache-Aside(旁路缓存)策略工作原理代码示例优缺点分析适用场景策略二:Re

Android实现定时任务的几种方式汇总(附源码)

《Android实现定时任务的几种方式汇总(附源码)》在Android应用中,定时任务(ScheduledTask)的需求几乎无处不在:从定时刷新数据、定时备份、定时推送通知,到夜间静默下载、循环执行... 目录一、项目介绍1. 背景与意义二、相关基础知识与系统约束三、方案一:Handler.postDel

Pandas利用主表更新子表指定列小技巧

《Pandas利用主表更新子表指定列小技巧》本文主要介绍了Pandas利用主表更新子表指定列小技巧,通过创建主表和子表的DataFrame对象,并使用映射字典进行数据关联和更新,实现了从主表到子表的同... 目录一、前言二、基本案例1. 创建主表数据2. 创建映射字典3. 创建子表数据4. 更新子表的 zb