标签为 [数论] 的文章

BZOJ2242 计算器

题目大意 你被要求设计一个计算器完成以下三项任务: 给定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<=10^9,为质数,1<=T<=10。 Solution 典型的NOIP三合一题,硬是把三道题合在了一起…… 前两问就不说了(一个快速幂,一个exgcd)…… 而要怎么解决第三问呢? 要用到BSGS(Baby-Step-Giant-Step)算法。用某方姓大佬的话: 就是枚举到根号的暴力 设x=im-j $ y^x=y^{im-j}\equiv z(mod p)$即$ y^{i ......

BZOJ2186 沙拉公主的困惑

题目大意 有多组询问,每次询问$ (\sum_{i=1}^{N!} [gcd(i,M!)==1] )%R$ M<=N<=10,000,000 Solution 本来觉得需要各种反演,但发现只要用好$ \varphi$函数就可以。 一个显然的结论,如果$ gcd(x,M!)=1$,则$ gcd(x+k(M!),M!)=1(k\in\mathbb{N})$ 而因为N!是M!的倍数,所以答案就变成了 $$(\sum_{i=1}^{M!}[gcd(i,M!)==1])(N!/M!)$$ $$=\varphi(M!)(N!/M!)$$ $$=M!\prod_{(p|M!)\land(p\in prime)}(p-1)/p(N!/M!)$$ $$=N!\prod_{(p|M!)\land(p\in prime)}(p-1)/p$$ 所以只要预处理出每个M以内的素数及其逆元,还有每个数的阶乘 ......

BZOJ3994 约数个数和

题目大意 设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<m,然后就可以转化式子了。$$\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{u|i}\sum_{v|j}\varepsilon(gcd(u,v))$$ $$=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{u|i}\sum_{v|j}\sum_{(d|u)\land(d|v)}\mu(d)$$ $$=\sum_{d=1}^{n}\mu(d)\sum_{u=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{v=1}^{\lfloor\frac{m}{d}\rfloor}\lfloor\frac{n}{d ......

BZOJ2301 Problem b

题目大意 对于给出的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(a-1,d)-f(b,c-1)+f(a-1,b-1)。所以只要求f(n,m)。 令$ n1=\lfloor\frac{n}{k}\rfloor$,$ m1=\lfloor\frac{m}{k}\rfloor$;且设n<=m $$f(n,m)=\sum_{i=1}^{n1}\sum_{j=1}^{m1}\varepsilon(gcd(i,j))$$ $$=\sum_{i=1}^{n1}\sum_{j=1}^{m1}\mu(gcd(i,j))*\mathrm{1}$$ $$=\sum_{i=1}^{n1}\sum_{j=1}^{m1}\sum_{(d|i)\land(d|j)}\mu(d)$$ $$=\s ......

BZOJ 3561 DZY Loves Math VI

题目传送门 Solution 很明显是莫比乌斯反演啦 令p=gcd(i,j),且n<m $$=\sum_{i=1}^{n}\sum_{j=1}^{m}{(\frac{i}{p})}^p{(\frac{j}{p})}^{p}{p}^{p}$$ $$=\sum_{p=1}^{n}\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{p}\rfloor}{(ijp)}^p\cdot\varepsilon(gcd(i,j))$$ $$=\sum_{p=1}^{n}p^p\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{p}\rfloor}{(ij)}^p\cdot\mu(gcd(i,j))\ast\mathrm{1}$$ $$=\sum_{p=1}^{n}p^p\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{j=1}^{\lfloor\fra ......

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\in p}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}(\mu*1)(gcd(i,j))$$ $$=\sum_{d\in p}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{k|i,k|j}\mu(k)$$ $$=\sum_{d\in p}\sum_{k=1}^{\lfloor\frac{n}{d}\rfloor}\mu(k)\lfloor\frac{n}{dk}\rfloor\lfloor\frac{n}{dk}\r ......