【bzoj4407】【于神之怒加强版】【莫比乌斯反演】

2024-02-20 15:38

本文主要是介绍【bzoj4407】【于神之怒加强版】【莫比乌斯反演】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Description

给下N,M,K.求

i=1nj=1mgcd(i,j)kmod(109+7)

Input

输入有多组数据,输入数据的第一行两个正整数T,K,代表有T组数据,K的意义如上所示,下面第二行到第T+1行,每行为两个正整数N,M,其意义如上式所示。
Output

如题
Sample Input

1 2
3 3
Sample Output

20
HINT

1<=N,M,K<=5000000,1<=T<=2000
题解:
首先可以化成

d=1ndki=1ndnidmidu(i)

设T=i*d
则可以化成
T=1nnTmTd|Tdku(Td)

设f(T)= d|Tdku(Td)
只要求出f数组,处理每组查询就是o( n) 了。
考虑 dk 是积性函数,所以f(T)也是积性函数。
所以我们就可以在线筛中处理f数组。
然后搞个前缀和即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#define N 5000010
#define P 1000000007 
#define LL long long
using namespace std;
int T,k,p[N],f[N],pos;
LL n,m,g[N],u[N],ans;
LL power(LL a,int b){LL ans;a%=P;for (ans=1;b;a=a*a%P,b>>=1) if (b&1) ans=ans*a%P;return ans;
}
void pre(){u[1]=1;g[1]=1;for (int i=2;i<=n;i++){if (!f[i]){p[++p[0]]=i;u[i]=-1;g[i]=(power(i,k)-1+P)%P;}for (int j=1;j<=p[0]&&i*p[j]<=n;j++){f[i*p[j]]=1; if (i%p[j]==0){g[i*p[j]]=g[i]*power(p[j],k)%P;break;}u[i*p[j]]=-u[i];g[i*p[j]]=(g[i]*g[p[j]])%P;} }for (int i=1;i<=n;i++) g[i]=(g[i]+g[i-1])%P;
}
int main(){scanf("%d%d",&T,&k);n=N-10;pre();while (T--){scanf("%d%d",&n,&m);if (n>m) swap(n,m);ans=0;pos=0; for (int i=1;i<=n;i=pos+1){pos=min(n/(n/i),m / (m / i));ans+=(LL)(n / i)*(LL)(m / i)%P*(LL)(g[pos]-g[i-1]+P)%P;ans%=P;}printf("%lld\n",ans);  }  
}

这篇关于【bzoj4407】【于神之怒加强版】【莫比乌斯反演】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

hdu6053 TrickGCD 莫比乌斯反演

TrickGCD Time Limit: 5000/2500 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others) Problem Description You are given an array  A  , and Zhu wants to know there are how many d

学习笔记 ---- 莫比乌斯反演总结

文章目录 概述前置知识数论分块狄利克雷卷积积性函数 莫比乌斯函数定义性质 莫比乌斯反演因子形式倍数形式 例题周期性字符串互质数对[NOI2010D1T1]能量采集BZOJ2820 YY的GCD[SDOI2015] 约数个数和BZOJ4407 于神之怒加强版【BZOJ2693】jzptab最小公倍数之和[bzoj3529-Sdoi2014] 数表 练习题51nod 1675 序列变换BZOJ3

18041 分期还款(加强版)

### 自查思路 1. 检查输入数据的处理是否正确。 2. 检查判断条件 `p <= d * r` 是否正确。 3. 确认公式计算和输出格式是否正确。 ### 伪代码 1. 读取输入的贷款金额、每月还款额和月利率。 2. 判断是否可以还清贷款:    - 如果每月还款额小于贷款金额乘以月利率,则输出“God”。    - 否则,计算还清贷款所需的月份数:      - 使用公式 m = lo

BZOJ 2440 2301 莫比乌斯应用

http://www.lydsy.com/JudgeOnline/problem.php?id=2440 Description 小 X 自幼就很喜欢数。但奇怪的是,他十分讨厌完全平方数。他觉得这些 数看起来很令人难受。由此,他也讨厌所有是完全平方数的正整数倍的数。然而 这丝毫不影响他对其他数的热爱。  这天是小X的生日,小 W 想送一个数给他作为生日礼物。当然他不能送一 个小X讨厌

莫比乌斯反演 两种形式

莫比乌斯反演在数论中占有重要的地位,许多情况下能大大简化运算。那么我们先来认识莫比乌斯反演公式。   定理:和是定义在非负整数集合上的两个函数,并且满足条件,那么我们得到结论           在上面的公式中有一个函数,它的定义如下:       (1)若,那么     (2)若,均为互异素数,那么     (3)其它情况下     对于函数

CodeForces 547C. Mike and Foam 莫比乌斯反演

题意:给定一个长度为n的数列a,和q个操作(1<= n,q <= 2*10^5, 1 <= a[i] <= 5*10^5 ) 需要维护一个多重集合Q. 每个操作给出一个下标i,如果a[i]属于Q那么把a[i]从Q中拿走,如果a[i]不属于Q,那么把a[i]加入Q中。 每次操作后询问Q中,有多少对i,j满足条件 i<j 且 gcd(a[i],a[j])=1 这个性质的维护比较困难,直

IOI2000 邮局 加强版 题解

[IOI2000] 邮局 加强版 题解 考虑动态规划,设 f i , j f_{i,j} fi,j​ 为经过了 i i i 个村庄,正在建第 j j j​ 个邮局的最优距离。 以及 w i , j w_{i,j} wi,j​ 表示区间 [ i , j ] [i,j] [i,j]​ 内建一个邮局时的距离总和。 a a a 数组表示每个村庄的坐标编号。 朴素版状态转移方程: f

Python星载气溶胶数据处理与反演分析

在当前全球气候变化和环境污染问题日益突出的背景下,气溶胶研究显得尤为重要。气溶胶在大气中由直径范围在0.01微米至10微米固体和液体颗粒构成,直接或间接影响地球辐射平衡、气候变化和空气质量。尤其在“碳中和”目标的驱动下,研究气溶胶对“碳中和”的气候影响及其环境效应,不仅对科学研究具有重大意义,同时也为政策制定提供了重要依据。 MODIS(中分辨率成像光谱仪)和CALIOP(云-气溶胶偏振激光雷达

基于Python星载气溶胶数据处理与反演分析

原文链接:基于Python星载气溶胶数据处理与反演分析https://mp.weixin.qq.com/s?__biz=MzUzNTczMDMxMg==&mid=2247606689&idx=1&sn=bcdca97812e5e21e1bf539eafa49a48b&chksm=fa826046cdf5e95059f4ebc5ae6120b8e909883dd1d7c0eb4a5897e79df1

HDU 1695 GCD 容斥原理/莫比乌斯反演

题意: 给你两个区间[a,b],[c,d],还有一个k。让你从区间[a,b]中找出x,[c,d]中找出y,问共有多少组(x,y)使得gcd(x,y)=k。 (x,y)和(y,x)算一组。 思路: 参考:http://blog.csdn.net/yang_7_46/article/details/9072533 容斥。 普通容斥: *如果gcd(x,y)=k,则gcd(x/k