题目大意 你被要求设计一个计算器完成以下三项任务: 给定y,z,p,计算Y^Z Mod P 的值; 给定y,z,p,计算满足xy≡ z ( mod P )的最小非负整数; 给定y,z,p,计算满足y^x ≡ z ( mod P)的最小非负整数。 对于100%的数据,1<=y,z,p<=1 …

题目大意 有多组询问,每次询问$ (\sum_{i=1}^{N!} [gcd(i,M!)==1] )%R$ M<=N<=10,000,000 Solution 本来觉得需要各种反演,但发现只要用好$ \varphi$函数就可以。 一个显然的结论,如果$ gcd(x,M!)=1$,则$ g …

题目大意 设d(x)为x的约数个数。有多组询问,每次给定N、M,求$ \sum_{i=1}^{N}\sum_{i=1}^{m}d(i,j)$ Solution 有一个式子:$ d(n,m)=\sum_{i|n}\sum_{j|m}\varepsilon(gcd(i,j))$。可以自己证明一下。 设n …

题目大意 对于给出的n个询问,每次求$ \sum_{i=a}^{b}\sum_{j=c}^{d}[\gcd(i,j)==k]$。 Solution 如果令f(n,m)=$ \sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(i,j)==k]$, 则最后的答案ans=f(b,d)-f( …
BZOJ2818GCD

题目传送门 这是一道非常简单的莫比乌斯反演题 $$\sum_{d\in p}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}\varepsilon(gcd(i,j))$$ $$=\sum_{d\i …