51nod1584加权约数和
2024-09-02 18:59:34
题目大意:
求:
\[\sum_{i-1}^n\sum_{j=1}^nmax(i,j)\sigma(i*j)
\]
\]
题解
对于这个\(\max\),套路的把它转化成:
\[2*\sum_{i=1}^n\sum_{j=1}^ii*\sigma(i*j)-\sum_{i=1}^n i*\sigma(i*i)
\]
\]
对于前面的部分,我们可以:
\[\sum_{i=1}^{n}\sum_{j=1}^ii\sum_{a|i}\sum_{b|j}a*\frac{j}{b}[(a,b)==1]
\]
\]
\[\sum_{i=1}^{n}i\sum_{j=i}^n\sum_{a|i}\sum_{b|j}a*\frac{j}{b}\sum_{d|(i,j)}\mu(d)
\]
\]
\[\sum_{d=1}^n\mu(d)\sum_{i=1}^{\frac{n}{d}}i*d\sum_{a|i}a*d\sum_{j=1}^{i}\sum_{b|j}\frac{j}{b}
\]
\]
\[\sum_{d=1}^n\mu(d)d^2\sum_{i=1}^{\frac{n}{d}}i\sum_{a|i}a\sum_{j=1}^i\sum_{b|j}\frac{j}{b}
\]
\]
\[\sum_{d=1}^n\mu(d)d^2\sum_{i=1}^{\frac{n}{d}}g_i
\]
\]
\[\sum_{D=1}^n\sum_{d|D}\mu(d)d^2G_{D/d}
\]
\]
\[g_n=n*\sigma_n*\sum_{i=1}^n \sigma_i
\]
\]
这个\(g\)数组就可以线性预处理了。
后面的部分可以线性筛,姿势++。
代码
#include<bits/stdc++.h>
#define N 1000009
using namespace std;
typedef long long ll;
const int maxn=1000000;
const int mod=1000000007;
bool vis[N];
int prime[N];
ll mu[N],md[N],mdp[N],ans[N],g[N],sum[N],f[N];
ll sig[N],sig2[N];
inline ll rd(){
ll x=0;char c=getchar();bool f=0;
while(!isdigit(c)){if(c=='-')f=1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return f?-x:x;
}
inline void MOD(ll &x){x=x>=mod?x-mod:x;}
inline void prework(int n){
sig[1]=mu[1]=sig2[1]=md[1]=mdp[1]=1;
for(int i=2;i<=n;++i){
//cout<<i<<" "<<md[i]<<" "<<mdp[i]<<endl;
if(!vis[i]){
prime[++prime[0]]=i;
md[i]=mdp[i]=i;
mu[i]=mod-1;
sig[i]=i+1;
sig2[i]=(1ll*i*i%mod+i+1)%mod;
}
for(int j=1;j<=prime[0]&&(i*prime[j])<=n;++j){
vis[i*prime[j]]=1;
if(i%prime[j]==0){
mu[i*prime[j]]=0;
md[i*prime[j]]=prime[j];
mdp[i*prime[j]]=mdp[i]*prime[j];
sig[i*prime[j]]=(sig[i]+1ll*prime[j]*mdp[i]%mod*sig[i/mdp[i]]%mod)%mod;
sig2[i*prime[j]]=sig2[i]+(1ll*mdp[i]*mdp[i]%mod*md[i]%mod+
1ll*mdp[i]*mdp[i]%mod*md[i]%mod*md[i]%mod)*sig2[i/mdp[i]]%mod;
sig2[i*prime[j]]%=mod;
break;
}
mu[i*prime[j]]=mod-mu[i];
sig[i*prime[j]]=sig[i]*sig[prime[j]]%mod;
md[i*prime[j]]=mdp[i*prime[j]]=prime[j];
sig2[i*prime[j]]=sig2[i]*sig2[prime[j]]%mod;
}
}
for(int i=1;i<=n;++i)MOD(sum[i]=sum[i-1]+sig[i]);
for(int i=1;i<=n;++i){
g[i]=1ll*sig[i]*i%mod*sum[i]%mod;
MOD(sig2[i]=sig2[i-1]+sig2[i]*i%mod);
for(int j=i;j<=n;j+=i)MOD(f[j]+=g[i]*mu[j/i]%mod*(j/i)%mod*(j/i)%mod);
MOD(f[i]+=f[i-1]);
ans[i]=(f[i]*2-sig2[i]+mod)%mod;
}
}
int main(){
prework(maxn);
int T=rd(),ct=0;
while(T--){
int x=rd();ct++;
printf("Case #%d: %lld\n",ct,ans[x]);
}
return 0;
}
最新文章
- 数据结构与算法JavaScript (三) 链表
- dedecms 时间标签strftime和MyDate
- 一个未解决的samba问题
- Jenkins的Publish Over FTP Plugin插件参数使用
- ImagXpress中如何修改Alpha通道方法汇总
- android+apimonitor+genymotion
- 【原创】Tomcat集群环境下对session进行外部缓存的方法(1)
- 本地不安装oracle-client,使用pl/sql developer连接数据库
- Flexigrid自定义显示数据列
- <;pages validateRequest=";false";/>;在.net4.0中无效的问题
- Ubuntu开机自动挂载Windows分区
- Uva 511 Updating a Dictionary
- 自己写的angularJs排序指令【原创】
- BASH SHELL not a valid identifier
- Vue之vue-cli安装与简单调试
- JdbcTemolate类的介绍<;一>;
- MIPS指令学习二
- Web应用安全之点击劫持(CLICKJACKING)与X-FRAME-OPTIONS HEADER
- NYOJ 252 01串 普通dp
- JVM垃圾收集算法的选择
热门文章
- docker--docker仓库
- JavaSE_Java跨平台原理
- [转帖]linux screen 命令详解,xshell关掉窗口或者断开连接,查看断开前执行的命令
- swagger @ApiModel添加实体类不生效
- CentOS7搭建NTP服务器及客户端同步时间
- 【6.10校内test】T1 FBI树
- linux 隐藏显示终端光标
- 06: django+celery+redis
- org.apache.httpcomponents:httpclient 工具类
- 20170309工作笔记--------如何用好dialog,想变什么样就变成什么样