首页 > 其他分享 >数论

数论

时间:2024-03-07 16:45:46浏览次数:18  
标签:frac gcd 数论 sum varphi dd equiv

在线 \(O(1)\) 逆元

预处理 \([1, k]\) 逆元,找到一个 \(u\) 使得 \(xu \bmod p \leq k\),则 \(x^{-1}=(xu)^{-1} \cdot u\)。

设 \(x=qB+r\),其中 \(B=p^{1/3}\),\(xu=quB+ru\)。凭感觉 \(xu \bmod p\) 的分布很均匀,因此我们可以让 \(u\) 小一些。\(u \leq p^{1/3}\) 时 \(ru \leq p^{2/3}\)。只要让 \(qBu \bmod p \leq p^{2/3}\) 就行了。

我们进行预处理,对每个 \(q\) 找一个 \(u\) 让该条件满足。注意到 \(B,u\) 都不大,固定 \(B\) 和 \(u\),当 \(q\) 增加时式子只会增加 \(p^{2/3}\) 左右,远小于可行区间 \([kp, kp+p^{2/3}]\),因此我们可以直接让 \(q\) 跳跃,\(O(1)\) 找到下一个合法 \(q\)。总值域 \(p^{2/3}Bu\),跳跃时增加 \(p\),共跳跃 \(p^{-1/3}Bu\) 次,每次跳跃位于长度为 \(p^{2/3}\) 的区间中,带来 \(p^{2/3}/(Bu)\) 个 \(q\),故因此只有 \(p^{1/3}\) 个合法 \(q\)。一共 \(p^{1/3}\) 个 \(u\),故预处理的复杂度为 \(p^{2/3}\)。

P7325

参考自魏老师的题解 orz。

考虑贡献即为 \(af_{p-1}+bf_{p}\)。

\(f_n=f_{n-1}+f_{n-2}\) 的性质:在模 \(m\) 意义下有长度为 \(O(m)\) 的纯循环节。

首先有 \(af_{i-1}\equiv-bf_{i} \pmod m\),找到 \(d=\gcd(a, b, m)\) 并约去得到 \(\frac{a}{d} f_{i-1} \equiv \frac{b}{d}f_i \pmod{\frac{m}{d}}\),这里把 \(b\) 取反。

我们想要把 \(\frac{b}{d}\) 除到左边去。令 \(d'=\gcd(\frac{b}{d}, \frac{m}{d})\),注意到一定有 \(d' \perp a\),所以一定有 \(d' \mid f_{i-1}\),所以有 \(\frac{a}{d}\frac{f_{i-1}}{d'} \equiv \frac{b}{dd'}f_i \pmod {\frac{m}{dd'}}\),除过去得到 \(\frac{a}{d} (\frac{b}{dd'})^{-1}\frac{f_{i-1}}{d}\equiv f_i \pmod{ \frac{m}{dd'}}\),可以证明 \(\frac{f_{i-1}}{d'} \perp \frac{m}{dd'}\)。

提前处理出所有 \((d, d', f_p/(f_{p-1}/d') \bmod \frac{m}{dd'})\) 塞进 map 中,这囊括了答案的所有信息。

有结论 \(d'=\gcd(f_{p-1},\frac{m}{d})\),因此 \(d'\) 不需要枚举。复杂度大概是 \(O(m \log \log m + n) \log m\),其中 \(m \log \log m\) 是 \(m\) 的约数和的数量级。

P5572

\[\begin{aligned} & \sum_{i=1}^n\sum_{j=1}^m \varphi\left(\frac{ij}{\gcd^2(i, j)}\right) \\ = & \sum_{i=1}^n\sum_{j=1}^m \varphi\left(\frac{i}{\gcd(i, j)}\right) \varphi\left(\frac{j}{\gcd(i, j)}\right) \\ = & \sum_{d=1}^m \sum_{i=1}^{n/d} \sum_{j=1}^{m/d} \varphi(i) \varphi(j) [i \perp j] \\ = & \sum_{d=1}^m \sum_{d'=1}^{m/d} \mu(d') \sum_{i=1}^{n/dd'} \sum_{j=1}^{m/dd'} \varphi(id') \varphi(jd') \\ = & \sum_{T=1}^m \sum_{d \mid T} \mu(d) \left ( \sum_{i=1}^{n/d} \varphi(i) \right ) \left ( \sum_{j=1}^{m/d} \varphi(j) \right ) \\ \end{aligned} \]

设 \(f(n, d) = \sum_{i=1}^{n} \varphi(i)\),这可以以 \(O(n \ln n)\) 的复杂度预处理。

原式变为 \(\sum_{T=1}^m \sum_{d \mid T} \mu(d) f(n/d, d) f(m/d, d)\)。

考虑根号分治,当 \(T < \sqrt{n}\) 时,枚举 \(d\)。否则设 \(g(n, m, s) = \sum_{T=1}^s \sum_{d \mid T} \mu(d) f(n, d) f(m, d)\),

exCRT

用 \(a+bx_i \equiv c_i \pmod {p_i}\) 合并方程,裴蜀定理判无解。

exBSGS

让方程不断除以 \(\gcd(a, p)\)。

$\frac{a}{d}a^{x-1} \equiv \frac{b}{d} \pmod {\frac{p}{d}} \Longrightarrow a^{x-1} \equiv $

P6610

用 CRT 转化为模奇素数。

注意到 \(a^2 \equiv x \pmod p\) 的解的个数是 \(x^{\frac{p-1}{2}}+1\),我们要求的即

\(\newcommand \L[2]{(\frac{#1}{#2})}\) \(\sum_{a}(\L{a}{p}+1)(\L{x-a}{p}+1) = p+\sum_a \L{ax-a^2}{p} = p+ \sum_{a=1}^{p-1} \L{x/a-1}{p}\)。

注意到 \(x \neq 0\) 时 \(a/x\) 取遍一个缩系,而缩系内勒让德记号可一一对应得到 \(0\),故答案为 \(p-\L{-1}{p}\)。\(x=0\) 时原式即 \(p+(p-1)\L{-1}{p}\)。

标签:frac,gcd,数论,sum,varphi,dd,equiv
From: https://www.cnblogs.com/purplevine/p/18059243

相关文章

  • P5655 基础数论函数练习题 题解
    分析考虑莫队。令$S=\operatorname{lcm}(a_l,a_{l+1},a_{l+2},\dots,a_{r-1})$。则对于新加进来的$a_r$,有:$$\operatorname{lcm}(a_l,a_{l+1},a_{l+2},\dots,a_{r-1},a_r)\=\operatorname{lcm}(S,a_r)\=\frac{S\timesa_r}{\gcd(S,a_r)}$$很容易发现,$S$在不取模的情况下会......
  • 数论小记
    gcd辗转相除法,也可以直接用__gcd。线性筛保证每个数只会被其最小的质数筛掉,复杂度\(O(n)\),也可以用来处理积性函数,通常作为更复杂的筛法的预处理。exgcd可用于求解不定方程:\(ax+by=gcd(a,b)\)推导如下:\[ax+by=gcd(a,b)=gcd(b,a\bmodb)=bx'+(a\bmodb)y'......
  • (数论)裴蜀定理
    裴蜀定理内容:${ax+by=c,x\inZ^*,y\inZ^*}$成立的充要条件是${\gcd(a,b)|c}$。$Z^*$表示正整数集。 设${s=\gcd(a,b)}$,显然${s|a}$,并且${s|b}$又因为${x,y\inZ^*}$所以${s|ax,s|by}$显然要使得之前的式子成立,则必须满足$c$是$a$和$b$的公约数的倍数又因为$x$和$y$是......
  • 杜教筛——亚线性处理数论函数求和
    问题引入给定一个数论函数\(f(x)\),求\(\sum\limits_{i=1}^nf(i)\)。对\(n\le10^7\)甚至\(n\le10^8\)都是好做的,\(\mathcalO(n)\)解决即可,但如果\(n<2^{31}\)呢?这就需要亚线性时间复杂度的算法,杜教筛就是其一。杜教筛杜教筛是一种能在幂时间\(\mathcalO(......
  • 花神的数论题(数位dp)
    花神的数论题题目描述设\(\text{sum}(i)\)表示\(i\)的二进制表示中\(1\)的个数。给出一个正整数\(N\),花神要问你\(\prod_{i=1}^{N}\text{sum}(i)\),也就是\(\text{sum}(1)\sim\text{sum}(N)\)的乘积。数据范围\(1\leN\le10^{15}\)。解法首先我们要......
  • 基础数论学习笔记
    1.辗转相减利用辗转相减法求最大公约数,即\(gcd(a,b)\)。假设\(a>b\),则gcd(a,b)=gcd(a−b,b),不断的利用大的数减去小的数,就能得到最大公约数。1.证:若\(n,m(n>m)\)互质,则$(n-m),m$互质若不互质,则设\(n-m=k*a,m=k*b\)\(\thereforen-k*b=k*a......
  • Toyota Programming Contest 2024#2(AtCoder Beginner Contest 341)D - Only one of two
    目录链接题面题意题解代码总结链接D-Onlyoneoftwo题面题意求第\(k\)个只能被\(N\)或\(M\)整除的数题解\([1,x]\)中的能被\(n\)整除的数有\(\lfloor\frac{x}{n}\rfloor\)个\([1,x]\)中的能被\(m\)整除的数有\(\lfloor\frac{x}{m}\rfloor\)个\([1,x]\)中的能被\(n\)......
  • 数论函数
    数论函数常见数论函数\(\epsilon(n)=[n=1]\)\(I(n)=1...\)\(id(n)=n\)\(id^k(n)=n^k\)\(\mu\)莫比乌斯函数\(\phi\)欧拉函数\(\tau\)约数个数\(\sigma\)约数和欧拉函数\(\phi(n)\)表示的是小于等于n和n互质的数的个数,是积性函数\(\phi(p^k)=p^k-p^{k-1}\)\(n=\sum_......
  • 数论分块性质优化DP状态
    6311.mobitel给定一个r行s列的矩阵,每个格子里都有一个正整数。问如果从左上角走到右下角,且每次只能向右或向下走到相邻格子,那么使得路径上所有数的乘积不小于n的路径有多少条?对于100%的数据,1<=r,s<=300,1<=n<=10^6,矩阵中的数不超过10^6。so,一个普通的思想就是设f[......
  • 【学习笔记】关于数论与平面几何的一切
    快速幂人话求\(a\)的\(n\)次方,其实就是根据二进制唯一分解定理给\(a^n\)拆成\(\log{n}\)个\(a^{2^i}\),递推求出从\(a^0\)到\(a^{2^i}\)每个数,如果\(n\)的二进制第\(i\)位为1,则将答案乘上\(a^{2^i}\)llQpow(lla,llb){//一开始a就是a的一次方llans=1;while(b......