【BZOJ3309】DZY Loves Math 解题报告
2024-10-19 12:36:34
【BZOJ3309】DZY Loves Math
Description
对于正整数\(n\),定义\(f(n)\)为\(n\)所含质因子的最大幂指数。例如\(f(1960)=f(2^3×5^1×7^2)=3\),\(f(10007)=1\),\(f(1)=0\)。
给定正整数\(a,b\),求\(\sum\limits_{a_i=1}\sum\limits_{b_j=1}f(\gcd(i,j))\)。
Input
第一行一个数\(T\),表示询问数。
接下来\(T\)行,每行两个数\(a,b\),表示一个询问。
Output
对于每一个询问,输出一行一个非负整数作为回答。
HINT
\(T≤10000\)
\(1≤a,b≤10^7\)
推式子可以得到
\[\sum_{T=1}^{\min(a,b)}\lfloor\frac{a}{T}\rfloor\lfloor\frac{b}{T}\rfloor\sum_{d|T}f(d)\mu(\frac{T}{d})
\]
\]
设\(g(T)=\sum_{d|T}f(d)\mu(\frac{T}{d})\),想一下卷积发现没啥用,然后我就放弃了。
浪费了一次打表的大好机会...打表可以发现\(g\)只有\(01\)两种值,但是没什么显然的性质,于是我们可以暴力按意义分类讨论取\(0\)或者\(1\)
然后我们讨论一下,设\(p\)代表质数
\(g(p)=1\)
然后在计算式中令\(\frac{T}{d}\)的幂全为\(0\)或\(1\),这样\(\mu\)才能产生贡献。
这样的话可以发现\(f(d)\)只有两种取值\(f(T)\)与\(f(T-1)\),暴力讨论这两种取值。
可以得到式子\(g(T)=-\sum_{d|x\&\&f(d)\not=f(x)}\mu(\frac{x}{d})\)
然后继续讨论可能取的\(01\)情况,发现如果幂全相等,可以取\((-1)^{k+1}\),\(k\)为约数个数
否则就取\(0\)
线筛的时候维护一下最小质因子的幂数和最小质因子的幂
Code:
#include <cstdio>
#include <algorithm>
#define ll long long
const int N=1e7;
using std::min;
int pri[N+10],ispri[N+10],a[N+10],b[N+10],cnt;
ll f[N+10],ans,n,m;
void init()
{
for(int i=2;i<=N;i++)
{
if(!ispri[i])
{
b[i]=pri[++cnt]=i;
f[i]=a[i]=1;
}
for(int j=1;j<=cnt&&i*pri[j]<=N;j++)
{
ispri[i*pri[j]]=1;
if(i%pri[j]==0)
{
a[i*pri[j]]=a[i]+1;
b[i*pri[j]]=b[i]*pri[j];
if(i==b[i]) f[i*pri[j]]=1;
else f[i*pri[j]]=a[i/b[i]]==a[i]+1?-f[i/b[i]]:0;
break;
}
else
{
a[i*pri[j]]=1,b[i*pri[j]]=pri[j];
f[i*pri[j]]=a[i]==1?-f[i]:0;
}
}
}
for(int i=1;i<=N;i++) f[i]+=f[i-1];
}
int main()
{
init();int T;scanf("%d",&T);
while(T--)
{
ans=0;
scanf("%lld%lld",&n,&m);
for(ll l=1,r;l<=min(n,m);l=r+1)
{
r=min(n/(n/l),(m/(m/l)));
ans+=(n/l)*(m/l)*(f[r]-f[l-1]);
}
printf("%lld\n",ans);
}
return 0;
}
2018.12.15
最新文章
- 魔性の分块 | | jzoj1243 | | 线段树の暴力
- Express调用mssql驱动公共类dbHelper
- js立即执行函数: (function ( ){...})( ) 与 (function ( ){...}( )) 有区别?
- MATLAB做主成分分析(PCA)
- hdu 4462(状态压缩)
- 基于heartbeat的单播方式实现tomcat高可用
- JavaFX 2.0+ WebView /WebEngine render web page to an image
- 使用django建博客时遇到的URLcon相关错误以及解决方法。错误提示:类型错误:include0获得一个意外的关键参数app_name
- mt6577驱动开发 笔记版
- 【入门】Spring-Boot项目配置Mysql数据库
- RPC----Hadoop核心协议
- [DOM基础]offsetHeight,clientHeight,scrollHeight,innerHeight,outerHeight等属性的解释
- Python写一个京东抢券脚本
- JS数据的基本类型
- QOpenGLFunctions的使用(2)
- layui数据表格的td模板
- Maven实战——常用Maven插件介绍
- js audio 播放音乐
- js数组去重的几种方法
- 课堂实验-String类和Arrays类