hdu6390 /// 欧拉函数+莫比乌斯反演 筛inv[] phi[] mu[]
2024-09-06 05:20:21
题目大意:
给定m n p 求下式
题解:https://blog.csdn.net/codeswarrior/article/details/81700226
莫比乌斯讲解:https://www.cnblogs.com/peng-ym/p/8647856.html
莫比乌斯的mu[]:https://www.cnblogs.com/cjyyb/p/7953803.html
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define INF 0x3f3f3f3f
#define mem(i,j) memset(i,j,sizeof(i))
const int N=1e6+; LL mu[N], phi[N];
LL inv[N]; int n,m,p; void initinv() {
inv[]=;
for(int i=;i<N;i++)
inv[i]=inv[p%i]*(LL)(p-p/i)%p;
} // 逆元
void init() {
for(int i=;i<N;i++) phi[i]=i;
for(int i=;i<N;i++)
if(i==phi[i]) {
for(int j=i;j<N;j+=i)
phi[j]=phi[j]/i*(i-);
}
mem(mu,); mu[]=;
for(int i=;i<N;i++)
for(int j=i*;j<N;j+=i)
mu[j]-=mu[i];
} // 欧拉 莫比乌斯 LL moblus(int a,int b,int g) {
LL res=; a/=g,b/=g;
/// gcd(1~a,1~b)=g -> gcd(1~a/g,1~b/g)=1
for(int i=;i<=min(a,b);i++)
res+=(LL)mu[i]*(a/i)*(b/i);
/// mu[i] * (1~a,1~b)中[gcd=g或g的倍数]的数量
return res;
} int main()
{
init();
int t; scanf("%d",&t);
while(t--) {
scanf("%d%d%d",&m,&n,&p);
LL ans=; initinv();
for(int i=;i<=min(m,n);i++) {
LL uF=moblus(n,m,i)%p;
ans=(ans+uF*i%p*inv[phi[i]]%p)%p;
}
printf("%lld\n",ans);
} return ;
}
最新文章
- rsa互通密钥对生成及互通加解密(c#,java,php)
- SSM 三大框架整合
- 如何删除或重置spfile中的参数
- ASP.NET发布后,功能不响应
- JS对URL字符串进行编码/解码分析
- 基于RESTful标准的Web Api
- JDBC的基本步骤
- 空格和TAB键混用错误:IndentationError: unindent does not match any outer indentation level
- Android开发之Java必备基础
- 6、android开发中遇到的bug整理
- 在Cubieboard上关闭irqbalance服务避免内存泄漏
- 《APUE》第五章练习1
- XSS脚本攻击漫谈
- Azure VM对远程桌面登录的支持-示例
- sift算法c语言实现
- android 中的ExpandableListView取消一级图标
- SOFA 源码分析 —— 服务发布过程
- Uncaught TypeError: Cannot read property ‘split’ of undefined
- readfile() file_get_content f
- 2018-2019-20175334实验一《Java开发环境的熟悉》实验报告