bzoj 3518 Dirichlet卷积
2024-09-28 12:02:13
详情见代码,回头再填坑。。。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define int long long
#define p 1000000007
using namespace std;
int n,m;
int phi[],su[],pr[],cnt;
void shai()
{
phi[]=;
for(int j=;j<=;j++)
{
if(!phi[j])phi[j]=j-,su[++cnt]=j,pr[j]=j;
for(int i=;su[i]<=pr[j]&&i<=cnt&&su[i]*j<=;i++)
{
pr[su[i]*j]=su[i];
if(!phi[su[i]*j])phi[su[i]*j]=su[i]*j;
if(su[i]==pr[j])phi[su[i]*j]=phi[j]*su[i];
else phi[su[i]*j]=phi[j]*(su[i]-);
}
}
}
signed main()
{
shai();
scanf("%lld%lld",&n,&m);
int ans=;
ans+=n*(n-)*(n-)*m/;ans%=p;
ans+=m*(m-)*(m-)*n/;ans%=p;
int tmp=;
for(int i=;i<=min(n-,m-);i++)tmp=(tmp+m*n%p*phi[i]*((n-)/i)%p*((m-)/i))%p;
for(int i=;i<=min(n-,m-);i++)tmp=(tmp+phi[i]*i%p*i%p*(((n-)/i)*(+(n-)/i)/)%p*(((m-)/i)*(+(m-)/i)/)%p)%p;
for(int i=;i<=min(n-,m-);i++)tmp=(tmp-n*phi[i]%p*i%p*((n-)/i)%p*((((m-)/i)*(+(m-)/i)/)%p)%p+p)%p;
for(int i=;i<=min(n-,m-);i++)tmp=(tmp-m*phi[i]%p*i%p*((m-)/i)%p*((((n-)/i)*(+(n-)/i)/)%p)%p+p)%p;
tmp-=((+n-)*(n-)/)%p*((+m-)*(m-)/)%p;tmp=(tmp+p)%p;
ans=(ans+tmp*)%p;
printf("%lld\n",ans);
return ;
}
最新文章
- Android 天气曲线
- wordpress后台打开慢/卡顿的解决方法
- SQLite简介
- 在C语言控制台程序中播放MP3音乐
- GitHub删除文件
- TFS实现需求工作项自动级联保存
- 利用AD采集获取外部温度传感器的值
- Java判断水仙花数
- springboot使用内部tomcat启动和外部tomcat启动的区别
- 【XSY2523】神社闭店之日 莫比乌斯反演
- java集合 线程安全
- 在屏幕拖拽3D物体移动
- Java+selenium 爬Boss直聘中职位信息,薪资水平和职位描述
- Page Cache, the Affair Between Memory and Files.页面缓存-内存与文件的那些事
- 671. Second Minimum Node In a Binary Tree
- Guideline 2.1 - Information Needed
- 廖雪峰Java1-2程序基础-5浮点数运算
- 处理No CPU/ABI system image for target的方法
- Velocity工作原理解析和优化
- amazeui笔记-web组件